Finden einer Quelle eines gerichteten azyklischen Graphen in linearer Zeit

Bei einem gerichteten azyklischen Graphen ist ein Scheitelpunkt eine Quelle, wenn sein Grad Null ist, was bedeutet, dass er nur ausgehende Bögen hat. $D = (V,A)$ $v \in V$

Gibt es einen linearen Zeitalgorithmus, um eine Quelle in einem bestimmten gerichteten azyklischen Graphen zu finden?

Folgefrage: Kann man in linearer Zeit alle Quellen finden?

algorithms graph-theory Breezeintopl
quelle

Mit root meinen Sie einen Knoten, der alle ausgehenden Kanten und keine eingehenden Kanten hat? In diesem Fall kann es mehr als eine Wurzel geben.

Paresh

Ja, du hast recht. Deshalb sage ich "eine Wurzel", aber nicht "die Wurzel".

Breezeintopl

Ist in diesem Fall die Definition für einen linearen Zeitalgorithmus nicht ausreichend?

Paresh

Wie ist die Datenstruktur? Erhalten Sie eine Adjazenzmatrix, Nachbarschaftslisten, Adjazenzliste oder was? Können Sie die (eingehende) Nachbarschaft eines Scheitelpunkts zeitlich proportional zu seiner Größe überprüfen?

Pål GD

Wenn Sie in der Anzahl der Eckpunkte linear meinen, sollten Sie dies angeben. Außerdem sind Adjazenzlisten für gerichtete Diagramme nicht eindeutig. Listen Sie eingehende Kanten, ausgehende Kanten, beide in separaten Listen oder beide zusammen auf?

Yuval Filmus

Antworten:

Wie Yuval erwähnt, ist die Datenstruktur hier wichtig. Ich werde versuchen, eine Lösung für einige der Arten von Adjazenzlisten zu finden:

Liste der eingehenden Kanten : Für jeden Knoten gibt es eine Liste von Scheitelpunkten, von denen zu diesem Knoten eine eingehende Kante stammt. Sie können einfach alle Scheitelpunkte scannen und prüfen, ob die Größe ihrer Adjazenzliste oder nicht. Eine Liste der Größe bedeutet, dass keine Kanten eingehen. Der Knoten ist also entweder eine Quelle oder nicht verbunden. Unter der Annahme eines verbundenen Graphen erhalten Sie bei diesem Scan jedes Scheitelpunkts eine Liste aller Quellen (oder Sie können anhalten, nachdem Sie eine gefunden haben) in - Zeit - linear in der Anzahl der Scheitelpunkte . $0$ $0$ $O(|V|)$
Liste der ausgehenden Kanten : Für jeden Knoten gibt es eine Liste von Scheitelpunkten, zu denen eine gerichtete Kante von diesem Knoten führt. Behalten Sie eine Bitfolge bei, wobei jedes Bit einen auf 0 initialisierten Scheitelpunkt darstellt. Beginnen Sie ab dem ersten Knoten mit dem Durchsuchen der Liste nach Scheitelpunkten, zu denen von diesem eine ausgehende Kante ausgeht. Jeder solche Knoten (Nachbar) kann keine Quelle sein, setzen Sie also das entsprechende Bit in der Bitfolge. Am Ende sind alle Scheitelpunkte, deren entsprechende Bits noch nicht gesetzt sind, die Quellscheitelpunkte. Sie können dies zeitlich linear in der Größe des Graphen tun - . $O(|V| + |E|)$
$O(|V| + |E|)$
Beide Listen getrennt : Wählen Sie einfach die eingehende Kantenliste aus und folgen Sie 1.

Wenn Sie die Auswahl der Datenstruktur in Ihren Händen haben, möchten Sie möglicherweise analysieren, welche Vorgänge Sie wie oft ausführen möchten, und eine geeignete Datenstruktur auswählen.

$|V|$ $|V|$

Paresh
quelle

| V |

$|V|$

| V |

$|V|$

Vielen Dank für Ihre Antwort! Ich denke, was ich meine, ist der zweite Fall, die ausgehende Liste. Übrigens, warum ist es O (| V | + | E |)? Ich kenne | E |, weil Sie alle Kanten scannen müssen, aber wo die | V | von? Vielen Dank!

Breezeintopl

Θ (| V | + | E |)

$\Theta(|V| + |E|)$

| E |

$|E|$

O (| V |)

$O(|V|)$

O (| V |^{2})

$O(|V|^2)$

| V |

$|V|$

$O(|V|-1)$

Reza
quelle

Wenn Ihre Datenstruktur keine Liste von In-Kanten für einen Knoten enthält, dauert das Auffinden des übergeordneten Knotens bereits O (m) (in Bäumen daher O (n) Zeit. Da der Pfad zur Wurzel des Baums linear sein kann lang, das ist nur eine quadratische Lösung. Aber wenn Sie In-Kanten haben, dann ist es trivial, einen Knoten mit 0 in Kanten zu finden.

adrianN

-1

Angenommen, Sie haben einen Graphen G = (V, E) im Adjazenzlistenformat. (Um hier klar zu sein, enthält die Liste alle ausgehenden Kanten von der Quelle). Sie können die Umkehrung des Graphen G in linearer Zeit konstruieren. Anschließend können Sie über das inverse Diagramm iterieren und alle Scheitelpunkte mit leerer Adjazenzliste erfassen. Diese Scheitelpunkte haben im inversen Diagramm keine ausgehende Kante, was bedeutet, dass sie im ursprünglichen Diagramm keine eingehenden Kanten haben. Daher sind dies Ihre Quellscheitelpunkte.

Die Laufzeit ist linear. Das Konstruieren der Umkehrung des Graphen dauert maximal O (| V | + | E |). Das Iterieren über die Umkehrung des Graphen benötigt O (| V |) Zeit.

MGB
quelle

Ehrlich gesagt klingt die Berechnung des Graphen invers nach einem schwierigeren Problem als das Finden der Quellen. Ich bezweifle, dass jemand, der nicht herausfinden kann, wie man an die Quellen kommt, herausfinden kann, wie man alle Kanten umkehrt.

David Richerby

@ DavidRicherby Sie sagten, die Berechnung des Graphen invers ist schwieriger. Wie definieren Sie härter? Wenn es die zeitliche Komplexität ist, kann dies in linearer Zeit erfolgen. Die Lösung finden Sie hier [link] ( stackoverflow.com/questions/40378152/… ). Die Frage betrifft eine lineare Zeitlösung, die die Quelle eines Graphen findet, und meine vorgeschlagene Lösung tut dies. Wenn Sie der Meinung sind, dass dies nicht der Fall ist, können Sie genau angeben und mir mitteilen, dass mein Algorithmus die Anforderungen an die lineare Zeit nicht erfüllt?

MGB

Ich meine konzeptionell schwieriger. Sie sagen, um diese Übung zu lösen, muss der Fragesteller nur eine andere Übung lösen, aber diese andere Übung scheint schwieriger zu sein als die erste.

David Richerby