Anzahl der erreichbaren Scheitelpunkte in der DAG für jeden Scheitelpunkt

Sei ein azyklisch gerichteter Graph, so dass der Außengrad eines beliebigen Scheitelpunkts . Für jeden Scheitelpunkt von wir die Anzahl der erreichbaren Scheitelpunkte zählen, indem wir einfach dfs von jedem Scheitelpunkt ausführen, und dies dauert Zeit. Gibt es einen besseren Weg, um dieses Problem zu lösen? $G(V,E)$ $O(\log{|V|})$ $G$ $O(|V||E|)$

ds.algorithms graph-theory graph-algorithms directed-acyclic-graph MikleB
quelle

Siehe auch : cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236

Radu GRIGore

@ Radu ist das ein direktes Duplikat? es klingt so

Suresh Venkat

@Suresh, im Vergleich zu meiner Frage hat diese eine Obergrenze für den Scheitelpunktgrad und fragt nicht nach Untergrenzen. Dies sind meiner Meinung nach kleine Unterschiede, daher würde ich es als Duplikat betrachten, aber ich habe kein starkes Gefühl dafür.

Radu GRIGore

ok also lassen wir es so wie es ist.

Suresh Venkat

Die Antwort von virgi auf meine Frage impliziert einen

-Algorithmus für diesen.

O (| V |^{2})

$O(|V|^2)$

Radu GRIGore

Antworten:

Der beste exakte Algorithmus wird in der Zeit O (min {mn, n ^ 2.38}) unter Verwendung einer schnellen binären Matrixmultiplikation ausgeführt. Es gibt jedoch einen Zufallsalgorithmus, der in der Zeit O (m + n) ausgeführt wird und die Anzahl der erreichbaren Knoten von jedem Knoten mit einem kleinen relativen Fehler schätzt. Weitere Informationen finden Sie im Artikel " Framework zur Größenschätzung mit Anwendungen für den transitiven Verschluss und die Erreichbarkeit" "von Edith Cohen.

user22547
quelle

-1

Ich bin hier kein Experte, ich werde es versuchen.

1) Da es sich um DAG handelt, sollte es einen Senkenscheitelpunkt haben, dh einen Scheitelpunkt mit outdegree 0. Suchen Sie einen Senkenscheitelpunkt, sagen Sie x, und fügen Sie {x} als erreichbaren Scheitelpunkt zu Nachbar (x) hinzu. Entfernen Sie x und wiederholen Sie den Vorgang, bis das Diagramm leer wird

Prabu
quelle

Da der Out-Degree begrenzt ist, scheint es sinnvoller zu sein, mit einer Quelle zu beginnen?

András Salamon

@ andras-salamon: nein, weil du nicht trivial weißt, wie viele Knoten von einer Quelle aus erreichbar sind. Sie tun das nicht (Null) für ein Waschbecken.

Martin B.

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

x

$x$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

-2

(Ähnlich wie Prabus Lösung ... aber detaillierter)

$N(v)$ $v$ $reach(v)$

$O(|V|+|E|)$
$v$ $reach(v) = \sum_{n\in N(v)} reach(n)$

$|E|$ $O(|V|+|E|)$

Martin B.
quelle