Traversal kierowanego grafu cyklicznego

Question

Mam cykl skierowany wykres. Rozpoczynając od liści, chcę propagować dane dołączone do każdego węzła poniżej wszystkich węzłów, do których można uzyskać dostęp z tego węzła. W szczególności muszę nadal przesuwać dane wokół wszelkich cykli, które są osiągane, dopóki cykle się nie ustabilizują.

Jestem całkowicie pewny, że jest to problem z przechodzeniem na wykres giełdowy. Mam jednak spore trudności, próbując znaleźć odpowiedni algorytm - myślę, że brakuje mi kilku kluczowych słów kluczowych w wyszukiwaniu.

Zanim spróbuję napisać własny algorytm O (n^3) o połowicznym brzuku, czy ktoś może wskazać mi właściwe rozwiązanie? A co to jest ?

Answer 1

Ponieważ wykres jest cykliczny (tzn. Może zawierać cykle), najpierw podzielę go na silnie połączone komponenty. A strongly connected component skierowanego wykresu jest podgraphiem, gdzie każdy węzeł jest osiągalny z każdego innego węzła w tym samym podgraphu. To dałoby zestaw podgrafów. Zauważ, że silnie połączonym składnikiem więcej niż jednego węzła jest efektywnie cykl.

Teraz, w każdym komponencie, każda informacja w jednym węźle ostatecznie znajdzie się w każdym innym węźle wykresu (ponieważ wszystkie są dostępne). Tak więc dla każdego podgraphu możemy po prostu pobrać wszystkie dane ze wszystkich węzłów i sprawić, że każdy węzeł będzie miał ten sam zestaw danych. Nie trzeba przechodzić przez kolejne cykle. Ponadto na końcu tego kroku wszystkie węzły w tym samym komponencie zawierają dokładnie te same dane.

Następnym krokiem byłoby zwinięcie każdego silnie połączonego komponentu w jeden węzeł. Ponieważ węzły tego samego komponentu mają te same dane, a zatem są w zasadzie takie same, operacja ta nie zmienia tak naprawdę wykresu. Nowo utworzony "super-węzeł" odziedziczy wszystkie krawędzie wychodzące lub wchodzące do węzłów komponentu z węzłów poza komponentem.

Ponieważ mamy załamał wszystkim silnie powiązane komponenty, nie będzie żadnych cykli wypadkowej wykresie (dlaczego? Bo gdyby nie było to cykl tworzony przez wynikowych węzłów, to oni wszystkie zostały umieszczone w ten sam składnik na pierwszym miejscu). Powstały wykres jest teraz Directed Acyclic Graph. Nie ma cykli, a prosta głębokość pierwszego przejścia od wszystkich węzłów z indegree = 0 (tj. Węzły, które nie mają krawędzi wejściowych), propagowanie danych z każdego węzła do jego sąsiednich węzłów (tj. Jego "potomków") powinno wykonać zadanie .