Speichern von Pfadinformationen in Kruskals Algorithmus

Question

Ich habe mit dem Kruskal-Algorithmus einen minimalen Spannbaum generiert und wollte wissen, wie Pfade gespeichert werden.

Dies ist mein minimaler Spannbaum

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------

Answer 1

Es hängt davon ab, wie viel zusätzlichen Speicherplatz Sie haben. Angenommen, Sie müssen platzsparend sein:

1. Richten Sie die Kanten so aus, dass die resultierende Struktur bei hat höchstens ein übergeordneter Knoten für jeden Knoten. Wie es geht? Wählen Sie einfach einen Knoten aus und machen Sie ihn zur Wurzel. Seine Kinder sind Knoten der ersten Ebene usw.
2. Speichern Sie nun das resultierende Diagramm im Format child-> parent (In Ihrer Tabelle können Sie Loc1-Spalte untergeordnet und Loc2-Spalte übergeordnet machen. Indizieren Sie es nach untergeordnetem Element)
3. Für zwei gegebene Knoten, a und y, deren Abstand berechnet werden muss, finden Sie ihre Elternsätze und sehen Sie, wo sie sich schneiden. Ex. Wenn das übergeordnete Element von x A ist, ist das übergeordnete Element von A B ... der übergeordnete Pfad ist ABCDLMN (wobei N die Wurzel ist). Ebenso, wenn die Elternwurzel für y EFLMN ist. Wie Sie sehen können, ist die niedrigste gemeinsame Wurzel für beide L. Abstand von x-> L ist 5, y-> L ist 3,=> Abstand zwischen x und y ist 5 + 3= 8.

   Komplexität: O (hlogn) wobei h die Höhe des Baums und n die Anzahl der Elemente im Baum ist (ich gehe von der Suchzeit für jeden Knoten in logn aus).