¿Cómo usar Union-Find, Minheap, Kruskal's y un algoritmo de clasificación para crear un árbol de expansión mínimo de costos? (C ++)
-
29-10-2019 - |
Pregunta
Pido disculpas si esta pregunta es un poco amplia, pero estoy teniendo dificultades para tratar de entender cómo crearía un árbol de expansión mínimo de costos. Esto está en C ++ si es importante.
Por lo que entiendo, usaría Kruskal para seleccionar los bordes de costo mínimo para construir el árbol de expansión. Mi pensamiento es leer los bordes en un minheap y de esa manera puede eliminar de la parte superior para obtener la ventaja con el costo mínimo.
Hasta ahora, solo he podido implementar el Minheap y los conjuntos para Union-Find, todavía no estoy seguro del propósito de un algoritmo de clasificación y un algoritmo de clasificación con el fin de crear un árbol de expansión.
Le agradecería cualquier consejo.
EDITAR: No me limito a Union Find, Minheap, Kruskals y un algorith de clasificación, ni debo hacer ninguno. Estos fueron solo los elementos sugeridos por el instructor.
No hay solución correcta