ich versuchen, diese Frage zu lösen, aber ich bin nicht sicher, ob meine Lösungungerichtete Grafik Was ist der mögliche minimale Spannbaum?
Dies ist meine Lösung: verwende ich Kruskal Algorithmus und ich wählen, um die Kanten, die (a) Blatt solution machen
danke.
Nein, die Antwort wird sein 9. Der Algorithmus nimmt Kanten:
ein < -> b mit Kosten 1: added a, b sind nun
ein < verbunden -> d mit Kosten 1: added a, b , d sind jetzt verbunden
b < -> d mit Kosten 4: SKIPPED
c < -> d mit Kosten 7: ADDED a, b, d, c sind jetzt verbunden, das ist der endgültige Spannbaum.
ein < -> c mit Kosten 8: SKIPPED
b < -> c mit Kosten 12: SKIPPED
So ist die Antwort 1 + 1 + 7 = 9.
aber so wird der Knoten (a) kein Blatt des Baumes ?? – Manal
Ah, ich verstehe. Dann ist deine Antwort richtig. Aber Sie können den Kruskal-Algorithmus nicht verwenden, weil er nicht garantiert, dass ein Knoten ein Blatt im endgültigen Spannbaum ist. Kruskal-Algorithmus würde Ihnen die Antwort geben, die ich gab, das ist 9. In solch einem kleinen Diagramm können Sie leicht alle möglichen aufspannenden Bäume finden und sie vergleichen. Aber wenn Sie möchten, dass ein Nicht-Brute-Force-Algorithmus mit dieser zusätzlichen Anforderung einen minimalen Spannbaum findet, benötigen Sie einen anderen Algorithmus als Kruskal, und ich weiß im Moment nicht, welchen Algorithmus Sie benötigen würden. –
danke, ich fand ein Beispiel für diese Quest und wie Sie sagten, keine Notwendigkeit für Kruskal. – Manal