Anzahl der Kanten zwischen zwei Knoten generieren

StackOverflow https://stackoverflow.com/questions/9389086

Frage

Ich habe diesen Minimum Spanning Tree mit dem Kruskal-Algorithmus generiert und es fällt mir schwer, Pfade zwischen zwei Knoten zu generieren.Kann mir jemand mit Pseudocode helfen?Ich habe versucht, Adjacency List und Adjaceny Matrix zu verwenden 

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
----------------------------------------------------

War es hilfreich?

Lösung

Wenn Sie nur einen Pfad zwischen zwei Knoten möchten, reicht eine Breitensuche auswürde den kürzesten Weg erzeugen (weil es ein minimaler Spannbaum ist).

Andere Tipps

Übergreifende Bäume haben per Definition keine Zyklen (oder Schleifen), sodass Sie höchstens einen Pfad (d. h. keine "Pfade" im Plural) zwischen zwei Knoten haben können.

Vielleicht verstehe ich die Frage nicht.Versuchen Sie herauszufinden, wie zwei bestimmte Knoten in Ihrem Baum verbunden sind?

Wenn ja, klingt es für mich nach der einfachsten rohen Kraft, bei der Sie nur von einem Punkt entlang seiner möglichen Kanten folgen würden, vielleicht indem Sie Möglichkeiten von einem Stapel aus schieben und platzen lassen, wäre O (Kanten)Laufzeit, die im Vergleich zum Kruskal-Algorithmus trivial wäre. Benötigen Sie etwas schneller?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top