Minimum Spanning Tree Kruskals Algorithmus

Question

Ich Kruskals Algorithmus die Zuordnung abgeschlossen von dem minimalen Spanning-Tree des folgenden Problems zu bestimmen:

Ich habe Städte, die alle miteinander verbunden werden müssen. Ich kann sie verbinden, indem ich Straßen zwischen ihnen baue oder einen Flughafen baue. Wenn ich einen Flughafen in einer Stadt baue, wird er mit allen anderen Städten verbunden, die Flughäfen haben.

Meine Zweifel an der nächsten Anforderung ist:

Im Fall von mehr als eine optimalen Lösung, ich habe das mit weniger Flughäfen zur Auswahl. Wie kann ich das auf möglichst effiziente Weise garantieren?

Answer 1

Im kruskal-Algorithmus sortieren und selektieren wir die Kanten in nicht-abnehmender Reihenfolge ihrer Gewichte.

Nehmen wir an, wir verwenden eine Datenstruktur (etwas wie Tupel), um Kanten als <source vertex,destination vertex, weight of edge between them> zu speichern. Wir sortieren und wählen Kanten in nicht abnehmender Reihenfolge ihrer Gewichte.

Jetzt im Fall von mehr als einer optimalen Lösung bevorzugen Sie die mit weniger Flughäfen. Fügen Sie also ein weiteres Feld (zB vom Typ boolean) in Ihre Datenstruktur ein, um zu speichern, ob der Zielknoten (Stadt) einen Flughafen hat. Dies sollte ungefähr wie <source vertex,destination vertex, weight of edge between them, has_destination_an_airport> aussehen. has_destination_an_airport ist true wenn der Zielknoten (Stadt) einen Flughafen hat, sonst false.

Wenn wir jetzt die Kanten in nicht abnehmender Reihenfolge ihrer Gewichte sortieren, wenn die Gewichte gleich sind, dann bevorzugen Sie diejenige, die keinen Flughafen hat, d. has_destination_an_airport ist false, wenn möglich.

Zusammenfassend, ordnungsgemäße Umsetzung von comparator zum Sortieren der Kanten wird die Magie tun.

Soweit asymptotische Zeit- und Raumkomplexität betroffen ist, ist es dasselbe wie das von Kruskals Algorithmus. Nur Overhead ist das eines zusätzlichen Feldes, das zu merken ist, wenn der Zielknoten einen Flughafen hat, was trivial ist.