¿Los algoritmos de Kruskal y Prim producen el mismo árbol de expansión mínimo?

9

Suponiendo que los bordes no están dirigidos, tienen un peso único y no tienen rutas negativas, ¿estos algoritmos producen los mismos árboles de expansión mínima?

Death_by_Ch0colate
fuente
3
Sí, y parecen producir el mismo MST. Pero eso no es definitivo.
Death_by_Ch0colate
2
Ok, eso es cierto, solo comprobando.
Mal
La respuesta sigue siendo positiva incluso si eliminamos la condición "sin trayectoria negativa"
John L.

Respuestas:

13

Encontré esto que indica que si se cumplen todas las condiciones que mencioné anteriormente, un gráfico necesariamente tiene un MST único. Por lo tanto, en términos de mi pregunta, los algoritmos de Kruskal y Prim necesariamente producen el mismo resultado.

Death_by_Ch0colate
fuente
7

Si el MST es único, todos los algoritmos lo producirán.

Si el MST no es único, los resultados pueden diferir debido a diferentes órdenes de procesamiento de nodos (incluso dos implementaciones distintas del mismo algoritmo pueden), pero los pesos totales serán idénticos. En este caso, el MST es un nombre inapropiado.

Yves Daoust
fuente
Ciertamente podrían, pero ¿ lo hacen ?
Raphael
44
@Raphael: respondí eso.
Yves Daoust
1
@Yves No, no lo hiciste. Dijiste que tal vez " tal vez " no es una garantía. Por ejemplo, si usted tiene algoritmos de ordenación, y son estables, no producen la misma salida, independientemente del algoritmo utilizado. Si no son estables, pueden producir los mismos resultados. Entonces, la pregunta es si esos algoritmos tienen una sensación de estabilidad en el tema y lo exhiben.
luk32
@ luk32: ¿leíste "incluso dos implementaciones distintas del mismo algoritmo pueden"? Por cierto, el algoritmo de ordenación estable produce el mismo resultado porque está definido de forma única, por lo que no tienen otra opción. Si no se requiere estabilidad, la solución no es única y diferentes implementaciones pueden comportarse de manera diferente.
Yves Daoust
Es justo, pero esa afirmación no es obvia. ¿Qué hace posible que la implementación no sea estable? ¿Hay algún tipo de clasificación involucrada y la estabilidad depende de esto?
luk32
2

Para agregar a la respuesta de Yves Daoust , el siguiente gráfico

Triángulo

En este gráfico, tenemos 3 nodos y 3 aristas, cada uno tiene el mismo peso. Obviamente, cualquier 2 aristas formará un MST para este gráfico. Sin embargo, los dos bordes elegidos dependerán no solo del algoritmo, sino también de la implementación del algoritmo. Por ejemplo, si almaceno los nodos en una lista, puedo visitarlos en un orden diferente que si almacenara los nodos en un conjunto, incluso si uso el mismo algoritmo MST a partir de ese momento.

De hecho, si mi implementación se basa en la aritmética del puntero (que hacen algunos contenedores en algunos idiomas), ¡incluso puedo elegir un MST diferente cada vez que ejecuto el algoritmo!

Cort Ammon
fuente
1
Tenga en cuenta que la publicación original establece que los bordes tienen un peso único; Por supuesto, esto garantiza un MST único.
wchargin
Ese último punto también se aplica cuando se usa, por ejemplo, seto dicten Python 3.3+: los hash se procesan con un valor diferente para cada ejecución para dificultar los ataques de denegación de servicio.
Jasmijn
@YvesDaoust ¡Lo siento mucho por eso!
Cort Ammon
@CortAmmon: no se preocupe, eso sucede.
Yves Daoust