Come usare sindacati, Minheap, Kruskal e un algoritmo di tipo per creare un costo minimo che si estende? (C ++)
-
29-10-2019 - |
Domanda
Mi scuso se questa domanda è un po 'ampia, ma sto avendo difficoltà a cercare di capire come creerei un costo minimo che lo spanning dell'albero. Questo è in C ++ se è importante.
Da quello che ho capito, useresti Kruskal per selezionare i bordi dei costi minimi per la costruzione dell'albero che si estende. Il mio pensiero è quello di leggere i bordi in un Minheap e in questo modo puoi rimuovere dall'alto per ottenere il bordo con il costo minimo.
Finora sono stato in grado di implementare MinHeap e set per Union-Find, non sono ancora sicuro dello scopo di Union-Find e di un algoritmo di smistamento allo scopo di creare un albero che attraversava.
Apprezzerei molto qualsiasi consiglio.
EDIT: non mi limito a Union Find, Minheap, Kruskals e un algorito di smistamento, né sono necessario per farne. Questi erano solo gli articoli suggeriti dall'istruttore.
Nessuna soluzione corretta