Ermitteln der Höhe aller Knoten in einer Gesamtstruktur

8

Ich habe einen Wald, dh Knoten mit gerichteten Kanten und keinen Zyklen (gerichtet oder ungerichtet). Ich definiere die Höhe eines Scheitelpunkts v als 0, wenn er keine eingehenden Kanten hat, oder die maximale Anzahl von Kanten, die umgekehrt verfahren werden müssen, um einen Scheitelpunkt der Höhe 0 zu erreichen. Geben Sie hier die Bildbeschreibung ein

Ich weiß auch, dass der durchschnittliche Grad eines Knotens eine kleine Konstante ist, etwa 2 oder so. Um die Höhe aller Eckpunkte zu ermitteln, kann ich mir zwei Algorithmen vorstellen:

Gehalgorithmus

  1. Gehen Sie durch und markieren Sie h=0 für Eckpunkte ohne eingehende Kanten.
  2. h=0

Grenzalgorithmus

  1. h=0
  2. 1
  3. Wiederholen Sie 2, bis sich nichts mehr hinter der Grenze befindet.

Meine Fragen:

  1. Gibt es einen Namen für dieses Problem und eine bekannte schnellste Lösung?
  2. h=0
grosse Bandbreite
quelle

Antworten:

7

Zunächst hängt es ein wenig davon ab, wie Sie auf Ihre Daten zugreifen können, um zu sagen, welche Algorithmen am besten funktionieren.

v

height(v)={(maxu child of vheight(u))+1if u is not a leaf0otherwise.

Sie können also nach allen Wurzeln suchen und dann die Höhen bestimmen, indem Sie eine Eroberung teilen. Sie werden jeden Scheitelpunkt höchstens zweimal berühren (Scannen nach Wurzeln + Durchqueren). Bei dem von Ihnen vorgeschlagenen Ansatz müssen Sie möglicherweise einige Scheitelpunkte mehrmals berühren.

Übrigens, da Sie einen Wald haben, haben Sie weniger Kanten als Eckpunkte, sodass Sie wissen, dass Sie einen durchschnittlichen Grad von weniger als zwei haben (und daher in linearer Zeit auf Wurzeln testen können).

A.Schulz
quelle
+1; rekursive Lösungen sind oft einfacher zu analysieren. Dies hängt auch davon ab, ob Sie bereits untergeordnete Zeiger haben oder nicht und ob Sie eine schleifenbasierte oder rekursionsbasierte Lösung wünschen.
Joe
Ich mag die Analyse! Kann jemand den Neulingen helfen, darauf hinzuweisen, wie dies auch in die iterative Form konvertiert werden kann?
HighBandWidth
4

Ich weiß nicht, ob dieses Problem einen offiziellen Namen hat oder nicht. Ihr Titel fasst es gut genug zusammen. Das Aufsteigen von den Knoten mit der Höhe 0 ist schnell, vorausgesetzt, Sie vermeiden Doppelarbeit. Angenommen, Sie haben einen Knoten mit vielen untergeordneten Elementen und einen langen Pfad über diesem Knoten zur Wurzel. Angenommen, die Höhen der einzelnen Kinder sind unterschiedlich. Jedes Kind kann die Höhe des betreffenden Knotens aktualisieren. Das ist ok. Sie sollten jedoch vermeiden, auch den langen Pfad über diesem Knoten zu aktualisieren, bis alle untergeordneten Knoten ihre Höhen gemeldet haben.

Der resultierende Algorithmus wird in linearer Zeit ausgeführt, und der Pseudocode würde ungefähr so ​​aussehen:

initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q
Joe
quelle
3

Ein Problem, das so ähnlich ist, dass es von Interesse sein könnte, ist "Paralleles Präfix für gerootete gerichtete Bäume". Der Algorithmus ermittelt die Anzahl der Kanten zur Wurzel von jedem Knoten. Die Wurzeln haben also den Wert 0, während beispielsweise der untere rechte Knoten den Wert zwei hat.

Beachten Sie, dass der folgende Algorithmus das allgemeinere Problem für gewichtete Kanten löst, Sie jedoch einfach W (i) für alle i auf 1 initialisieren können. Und der Nachfolger jedes Knotens i ist gegeben durch P (i) = j.

for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

Das Bild unten zeigt die "Halbierung" der Pfadlängen und macht die logarithmische Laufzeit leicht verständlich. Die berechneten Knotenhöhen werden jedoch nicht angezeigt.

Geben Sie hier die Bildbeschreibung ein

(aus "Einführung in parallele Algorithmen" von Joseph Jaja).

Bei Verwendung mehrerer Prozessoren ist es in O (lg n) -Zeit lösbar, verwendet jedoch O (n lg n) -Operationen. Es gibt einen Hack, um es auf lineare Arbeit zu bringen, aber es ist leicht involviert.

Die Unfun Cat
quelle
Vielen Dank! Was bedeutet S(i)?
HighBandWidth
Der Nachfolgeknoten. In der Iteration ist also einer der rechten Bäume, S (9) = 10, S (10) = 11, S (11) = 12, S (12) = 13 und W (9) = 1, W (10) = 1 , W (11) = 1, W (12) = 1. In Iteration zwei ist S (9) = 11, S (10) = 12, S (11) = 13, S (12) = 13 und W (9) = 2, W (10) = 2, W (11) = 2, W (12) = 1. In Iteration drei ist S (9) = 13, S (10) = 13, S (11) = 13, S (12) = 13 und W (9) = 2 + 2, W (10) = 2 + 1, W (11) = 2, W (12) = 1.
Die Unfun Cat
Sie müssen sich vorstellen, dass alle S (i) und W (i) gleichzeitig aktualisiert werden, wenn Sie versuchen, die Details herauszuarbeiten. Das mag dunkel sein, aber ich wollte es posten, weil es ein klassisches Parallelproblem ist und sehr nahe an dem liegt, was Sie beschrieben haben.
Die Unfun Cat