Ho letto l'algoritmo di Kruskal come è presentato su Wikipedia . Lì, dice che è un algoritmo nella teoria dei grafi che trova un albero spanning minimo per un grafo ponderato collegato.
Ma passando attraverso gli esempi che illustrano questo algoritmo non sono in grado di capire perché I loop sono evitati segnando alcuni dei bordi in rosso.
Qual è la ragione di questo?
L'algoritmo di Kruskal fornisce una spanning minima albero e un albero non ha cicli (cicli). Quindi l'algoritmo dovrebbe evitare la costruzione di loop nel trovare il sottografo con spanning minimo.
Devi già sapere che non puoi avere cicli in un albero. Pertanto, mentre si aggiunge un margine all'MST, è necessario assicurarsi che non venga creato alcun ciclo o ciclo. In secondo luogo nell'esempio pubblicato, il colore rosso viene utilizzato solo per chiarire che questo particolare collegamento non deve essere aggiunto all'MST poiché creerà un ciclo. Quindi i loop non vengono evitati facendo in modo che alcuni dei bordi rossi siano evitati piuttosto che non aggiungendo i bordi che collegano i vertici già connessi (ad esempio B e D nel passaggio 5 dell'esempio menzionato dall'utente) e tali collegamenti sono mostrati in rosso per evitare confusione
Leggi altre domande sui tag algorithms