Jak sprawdzić, czy wykres skierowany jest acykliczny? A jak nazywa się ten algorytm? Byłbym wdzięczny za odniesienie.
82
Jak sprawdzić, czy wykres skierowany jest acykliczny? A jak nazywa się ten algorytm? Byłbym wdzięczny za odniesienie.
Odpowiedzi:
Spróbowałbym posortować wykres topologicznie , a jeśli nie możesz, to ma cykle.
źródło
Wykonanie prostego przeszukiwania w głąb nie wystarczy, aby znaleźć cykl. Możliwe jest wielokrotne odwiedzanie węzła w DFS bez istniejącego cyklu. W zależności od tego, gdzie zaczynasz, możesz również nie przeglądać całego wykresu.
Możesz sprawdzić cykle w połączonym elemencie wykresu w następujący sposób. Znajdź węzeł, który ma tylko wychodzące krawędzie. Jeśli nie ma takiego węzła, istnieje cykl. Uruchom DFS w tym węźle. Podczas przechodzenia przez każdą krawędź sprawdź, czy krawędź wskazuje z powrotem do węzła już na stosie. Wskazuje to na istnienie cyklu. Jeśli nie znajdziesz takiej krawędzi, nie ma cykli w tym połączonym elemencie.
Jak zauważa Rutger Prins, jeśli twój wykres nie jest połączony, musisz powtórzyć wyszukiwanie na każdym podłączonym komponencie.
Jako odniesienie, silnie powiązany algorytm komponentów Tarjana jest ściśle powiązany. Pomoże Ci również znaleźć cykle, a nie tylko zgłosić, czy istnieją.
źródło
Lemat 22.11 dotyczący książki
Introduction to Algorithms
(wydanie drugie) stwierdza, że:źródło
Rozwiązanie 1:Algorytm Kahna do sprawdzania cyklu . Główny pomysł: utrzymuj kolejkę, w której węzeł o zerowym stopniu zostanie dodany do kolejki. Następnie oddzielaj węzeł jeden po drugim, aż kolejka będzie pusta. Sprawdź, czy istnieją wewnętrzne krawędzie węzła.
Rozwiązanie 2 : Algorytm Tarjan do sprawdzania silnie połączonego komponentu.
Rozwiązanie 3 : DFS . Użyj tablicy liczb całkowitych do oznaczenia aktualnego stanu węzła: np. 0 - oznacza, że ten węzeł nie był wcześniej odwiedzany. -1 - oznacza, że ten węzeł był odwiedzany i jego węzły podrzędne są odwiedzane. 1 - oznacza, że ten węzeł został odwiedzony i gotowe. Więc jeśli status węzła wynosi -1 podczas wykonywania DFS, oznacza to, że musi istnieć cykl.
źródło
Rozwiązanie podane przez ShuggyCoUk jest niekompletne, ponieważ może nie sprawdzić wszystkich węzłów.
Ma to złożoność czasową O (n + m) lub O (n ^ 2)
źródło
m = O(n^2)
ponieważ cały wykres ma dokładniem=n^2
krawędzie. Więc to jestO(n+m) = O(n + n^2) = O(n^2)
.Wiem, że to stary temat, ale dla przyszłych poszukiwaczy tutaj jest implementacja C #, którą stworzyłem (bez twierdzenia, że jest najbardziej wydajna!). Ma to na celu użycie prostej liczby całkowitej do identyfikacji każdego węzła. Możesz to udekorować w dowolny sposób, pod warunkiem, że obiekt węzła odpowiednio hashuje i jest równy.
W przypadku bardzo głębokich wykresów może to wiązać się z dużym narzutem, ponieważ tworzy hashset w każdym węźle na głębokości (są one niszczone na szerokość).
Wprowadzasz węzeł, z którego chcesz przeszukiwać, i ścieżkę do tego węzła.
Podczas sprawdzania cykli poniżej dowolnego podanego węzła, po prostu przekaż ten węzeł wraz z pustym hashsetem
źródło
Podczas wykonywania DFS nie powinno być żadnej tylnej krawędzi. Śledź już odwiedzone węzły podczas wykonywania DFS, jeśli napotkasz krawędź między bieżącym węzłem a istniejącym węzłem, to wykres ma cykl.
źródło
oto szybki kod, aby sprawdzić, czy wykres ma cykle:
Pomysł jest taki: normalny algorytm dfs z tablicą do śledzenia odwiedzanych węzłów i dodatkową tablicą, która służy jako znacznik dla węzłów, które prowadziły do bieżącego węzła, dzięki czemu kiedykolwiek wykonamy dfs dla węzła ustawiamy odpowiadający jej element w tablicy znaczników jako prawdziwy, aby kiedykolwiek napotkany już odwiedzony węzeł sprawdzał, czy odpowiadający mu element w tablicy znaczników jest prawdziwy, jeśli jest prawdziwy, to jest to jeden z węzłów, które sobie wpuszczają (stąd cycle), a sztuczka polega na tym, że za każdym razem, gdy dfs węzła zwraca, ustawiamy odpowiadający mu znacznik z powrotem na false, więc jeśli odwiedzimy go ponownie z innej trasy, nie damy się zwieść.
źródło
Właśnie miałem to pytanie w wywiadzie dla Google.
Sortowanie topologiczne
Możesz spróbować posortować topologicznie, czyli O (V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi. Graf skierowany jest acykliczny wtedy i tylko wtedy, gdy można to zrobić.
Rekurencyjne usuwanie liści
Rekurencyjnie usuwają węzły liści, dopóki ich nie ma, a jeśli pozostał więcej niż jeden węzeł, masz cykl. O ile się nie mylę, to jest O (V ^ 2 + VE).
W stylu DFS ~ O (n + m)
Jednak skuteczny algorytm DFS w najgorszym przypadku O (V + E) to:
function isAcyclic (root) { const previous = new Set(); function DFS (node) { previous.add(node); let isAcyclic = true; for (let child of children) { if (previous.has(node) || DFS(child)) { isAcyclic = false; break; } } previous.delete(node); return isAcyclic; } return DFS(root); }
źródło
Oto moja implementacja algorytmu węzła peel off leaf w Ruby .
źródło
Możesz użyć odwrócenia cyklu znajdowania z mojej odpowiedzi tutaj https://stackoverflow.com/a/60196714/1763149
def is_acyclic(graph): return not has_cycle(graph)
źródło