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?
fuente
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?
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.
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!
set
o dict
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.