Liczba osiągalnych wierzchołków w DAG dla każdego wierzchołka

Niech będzie grafem ukierunkowanym acyklicznie, tak że out-out dowolnego wierzchołka to . Dla każdego wierzchołka możemy policzyć liczbę osiągalnych wierzchołków, po prostu uruchamiając dfs z każdego wierzchołka, a to zajmie czas . Czy istnieje lepszy sposób na rozwiązanie tego problemu? $G(V,E)$ $O(\log{|V|})$ $G$ $O(|V||E|)$

ds.algorithms graph-theory graph-algorithms directed-acyclic-graph MikleB
źródło

Powiązane: cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236

Radu GRIGore 11.01.11

@Radu czy to prosty duplikat? to tak brzmi

Suresh Venkat

@Suresh, w porównaniu do mojego pytania, ta ma górną granicę stopnia wierzchołka i nie prosi o dolne granice. Są to, moim zdaniem, niewielkie różnice, więc uważam to za duplikat, ale nie czuję się mocno.

Radu GRIGore

ok, więc zostawimy to tak, jak jest.

Suresh Venkat,

Odpowiedź virgiego na moje pytanie oznacza dla tego algorytm

O (| V |^{2})

$O(|V|^2)$

Radu GRIGore

Odpowiedzi:

Najlepszy dokładny algorytm zadziała w czasie O (min {mn, n ^ 2,38}) przy użyciu szybkiego mnożenia macierzy binarnej. Istnieje jednak algorytm losowy, który działa w czasie O (m + n) i szacuje liczbę osiągalnych węzłów z każdego węzła z niewielkim błędem względnym, zapoznaj się z dokumentem „ Szacunek rozmiaru z aplikacjami do przejściowego zamykania i osiągalności przez Edith Cohen.

użytkownik22547
źródło

-1

Nie jestem tutaj ekspertem, spróbuję.

1) Ponieważ jest to DAG, powinien mieć wierzchołek zlewu, tzn. Wierzchołek z liczbą zerową 0. Znajdź wierzchołek zlewu powiedz x i dodaj {x} jako osiągalny wierzchołek do Neighbor (x). usuń x i powtarzaj proces, aż wykres stanie się pusty

Prabu
źródło

Ponieważ out-stopień jest ograniczony, bardziej przydatne byłoby zacząć od źródła?

András Salamon,

@ andras-salamon: nie, ponieważ nie wiadomo, ile węzłów jest dostępnych ze źródła. Nie robisz tego (zero) dla zlewu.

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

(Podobne do rozwiązania Prabu ... ale bardziej szczegółowe)

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

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

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

Martin B.
źródło