Jak sprawdzić, czy wykres skierowany jest acykliczny?

82

Jak sprawdzić, czy wykres skierowany jest acykliczny? A jak nazywa się ten algorytm? Byłbym wdzięczny za odniesienie.

nes1983
źródło
Kolejny przypadek przemawiający za jakimś sposobem „naprawienia” błędnych odpowiedzi na SO.
Sparr
2
Więc, umm, interesuje mnie głównie czas potrzebny na znalezienie tego. Więc potrzebuję tylko abstrakcyjnego algorytmu.
nes1983
musisz przejść przez wszystkie krawędzie i sprawdzić wszystkie wierzchołki, tak aby dolna granica wynosiła O (| V | + | E |). DFS i BFS mają tę samą złożoność, ale DFS jest łatwiejszy do kodowania, jeśli masz rekursję, ponieważ zarządza stosem za Ciebie ...
ShuggyCoUk
DFS to nie ta sama złożoność. Rozważmy wykres z węzłami {1 .. N} i krawędziami w postaci {(a, b) | a <b}. Ten wykres jest acykliczny, a mimo to DFS wyniesie O (n!)
FryGuy,
1
DFS nigdy nie jest O (n!). Odwiedza każdy węzeł raz i co najwyżej dwa razy każdą krawędź. Więc O (| V | + | E |) lub O (n).
Jay Conrod,

Odpowiedzi:

95

Spróbowałbym posortować wykres topologicznie , a jeśli nie możesz, to ma cykle.

FryGuy
źródło
2
Jak to się stało, że nie ma głosów? Jest liniowy na węzłach i krawędziach, znacznie lepszy od rozwiązań O (n ^ 2)!
Loren Pechtel,
5
W wielu przypadkach DFS (patrz odpowiedź J.Conrod) może być łatwiejsze, zwłaszcza jeśli i tak trzeba wykonać DFS. Ale oczywiście zależy to od kontekstu.
sleske
1
Porządkowanie
35

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ą.

Jay Conrod
źródło
2
BTW: Krawędź, która „wskazuje z powrotem na węzeł znajdujący się już na twoim stosie” jest często nazywana w literaturze „tylną krawędzią” z oczywistych powodów. I tak, może to być prostsze niż sortowanie wykresu topologicznie, zwłaszcza jeśli i tak musisz wykonać DFS.
sleske
Aby wykres był acykliczny, mówisz, że każdy połączony komponent musi zawierać węzeł z tylko wychodzącymi krawędziami. Czy możesz polecić algorytm do znajdowania połączonych komponentów (w przeciwieństwie do „silnie” połączonych komponentów) skierowanego grafu, do wykorzystania przez twój główny algorytm?
kostmo
@kostmo, jeśli wykres ma więcej niż jeden podłączony komponent, nie odwiedzisz wszystkich węzłów w swoim pierwszym DFS. Śledź odwiedzone węzły i powtarzaj algorytm z nieodwiedzonymi węzłami, aż dotrzesz do nich wszystkich. W zasadzie tak działa algorytm połączonych komponentów.
Jay Conrod,
6
Chociaż intencja tej odpowiedzi jest poprawna, odpowiedź jest myląca, jeśli używa się implementacji DFS opartej na stosie: stos używany do implementacji DFS nie będzie zawierał poprawnych elementów do przetestowania. Konieczne jest dodanie dodatkowego stosu do algorytmu używanego do śledzenia zbioru węzłów przodków.
Theodore Murdock
Mam wiele pytań dotyczących Twojej odpowiedzi. Opublikowałem je tutaj: stackoverflow.com/questions/37582599/…
Ari
14

Lemat 22.11 dotyczący książki Introduction to Algorithms(wydanie drugie) stwierdza, że:

Graf skierowany G jest acykliczny wtedy i tylko wtedy, gdy przeszukiwanie G w głąb nie daje tylnych krawędzi

Filipe Miguel Fonseca
źródło
1
To jest po prostu skrócona wersja odpowiedzi Jaya Conroda :-).
sleske
Jeden z problemów z tej samej książki wydaje się sugerować, że istnieje | V | algorytm czasowy. Odpowiedź jest tutaj: stackoverflow.com/questions/526331/ ...
Justin
9

Rozwiązanie 1Algorytm 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.

Chris Su
źródło
2

Rozwiązanie podane przez ShuggyCoUk jest niekompletne, ponieważ może nie sprawdzić wszystkich węzłów.


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Ma to złożoność czasową O (n + m) lub O (n ^ 2)


źródło
mój jest rzeczywiście niepoprawny - chociaż go
usunąłem,
3
O (n + m) <= O (n + n) = O (2n), O (2n)! = O (n ^ 2)
Artru
@Artru O (n ^ 2) w przypadku korzystania z macierzy sąsiedztwa, O (n + m) w przypadku korzystania z listy sąsiedztwa do przedstawiania wykresu.
0x450
Um ... m = O(n^2)ponieważ cały wykres ma dokładnie m=n^2krawędzie. Więc to jest O(n+m) = O(n + n^2) = O(n^2).
Alex Reinking
1

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.

  • W przypadku wykresu z pojedynczym węzłem głównym wysyłasz ten węzeł i pusty hashset
  • W przypadku wykresu z wieloma węzłami głównymi zawijasz to w foreach nad tymi węzłami i przekazujesz nowy pusty hashset dla każdej iteracji
  • Podczas sprawdzania cykli poniżej dowolnego podanego węzła, po prostu przekaż ten węzeł wraz z pustym hashsetem

    private bool FindCycle(int node, HashSet<int> path)
    {
    
        if (path.Contains(node))
            return true;
    
        var extendedPath = new HashSet<int>(path) {node};
    
        foreach (var child in GetChildren(node))
        {
            if (FindCycle(child, extendedPath))
                return true;
        }
    
        return false;
    }
    
Mateusz
źródło
1

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.

Santhosh
źródło
1

oto szybki kod, aby sprawdzić, czy wykres ma cykle:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

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ść.

m.eldehairy
źródło
1

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);
}
Tom Golden
źródło
0

Oto moja implementacja algorytmu węzła peel off leaf w Ruby .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end
neoneye
źródło