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?
graphs
trees
minimum-spanning-tree
Death_by_Ch0colate
fuente
fuente
Respuestas:
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.
fuente
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.
fuente
Para agregar a la respuesta de Yves Daoust , el siguiente gráfico
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!
fuente
set
odict
en Python 3.3+: los hash se procesan con un valor diferente para cada ejecución para dificultar los ataques de denegación de servicio.