Ich habe eine Grafik im Adjazenzmatrixformat und dieGrafik hat Bäume getrennt. Ich muss die MST jedes getrennten Baumes finden. Also sollte ich zuerst Subgraphen für jeden Baum finden und dann MST auf dem Baum verwenden oder gibt es einen besseren Ansatz / Algorithmus?
Antworten:
1 für die Antwort № 1Ich denke, ich habe es gefunden.
Kruskals Algorithmus und Borůvkas Algorithmus kannfinde den minimalen Spannwald in einem möglicherweise nicht verbundenen Graphen; Im Gegensatz dazu findet die grundlegendste Form des Prim-Algorithmus nur minimale Spannbäume in verbundenen Graphen.
Wenn Sie jedoch den Prim-Algorithmus für jede verbundene Komponente des Graphen separat ausführen, kann er auch dazu verwendet werden, die minimale Spanning-Gesamtstruktur zu finden