Algorithmus zu überprüfen, ob gerichteten Graphen stark verbunden ist,

StackOverflow https://stackoverflow.com/questions/1434787

Frage

Ich muß überprüfen, ob ein gerichteter Graph ist stark verbunden , oder, mit anderen Worten, wenn alle Knoten von jedem anderen Knoten (nicht unbedingt durch direkte Flanke) erreicht werden können.

Eine Möglichkeit, dies zu tun, auf jedem Knoten ein DFS und BFS läuft und sehen alle anderen noch erreichbar sind.

Gibt es einen besseren Ansatz, das zu tun?

War es hilfreich?

Lösung

Tarjan der stark verbundene Komponenten-Algorithmus (oder Gabow der variation) wird natürlich ausreichen; wenn es nur eine stark verbundene Komponente ist, dann wird die Graph stark verbunden.

Beide sind lineare Zeit.

Wie bei einem normalen Tiefensuche, verfolgen Sie den Status jedes Knotens: neu, gesehen, aber noch offen (es ist in dem Call-Stack) und gesehen und fertig. Darüber hinaus speichern Sie die Tiefe, wenn Sie zuerst einen Knoten erreicht, und die niedrigste solchen Tiefe, die von dem Knoten erreichbar ist (Sie wissen dies, nachdem Sie einen Knoten zu beenden). Ein Knoten ist die Wurzel einer stark verbundenen Komponente, wenn die niedrigste erreichbare Tiefe auf seine eigene Tiefe gleich ist. Dies funktioniert auch, wenn die Tiefe, mit dem Sie einen Knoten von der Wurzel erreichen ist nicht das Minimum möglich.

Um zu überprüfen, nur, ob die gesamte grafische Darstellung ist ein einzelner SCC, initiieren die dfs von jedem einzelnen Knoten, und wenn Sie fertig sind, wenn die niedrigste erreichbare Tiefe 0 ist, und jeder Knoten besucht wurde, dann ist die ganze Graph stark verbunden.

Andere Tipps

Betrachten Sie den folgenden Algorithmus.

  1. Starten Sie bei einem zufälligen Scheitel v des Graphen G und ein DFS(G, v) laufen.

    • Wenn DFS(G, v) alle anderen Knoten in dem Graphen G nicht erreichen kann, dann gibt es einige Vertex u, so dass es keinen gerichteten Weg von v zu u ist und somit G ist nicht stark verbunden .

    • Wenn es jede Ecke tut erreichen, dann gibt es einen gerichteten Weg von v zu jedem anderen Knoten in dem Graphen G.

  2. Kehrt die Richtung aller Kanten im gerichteten Graphen G .

  3. Wieder ein DFS laufen bei v starten.

    • Wenn die DFS jede Ecke nicht erreichen können, dann gibt es einige Vertex u, so dass in dem ursprünglichen Graphen gibt es keinen gerichteten Weg von u zu v.

    • Auf der anderen Seite, wenn es jede Ecke tut erreichen, dann in dem ursprünglichen Graphen gibt es einen gerichteten Weg von jedem Scheitelpunkt u v .

Wenn also G „geht“ sowohl DFSs, wird dringend verbunden. Da darüber hinaus eine DFS in O(n + m) Zeit abläuft, dieser Algorithmus läuft in O(2(n + m)) = O(n + m) Zeit, da es 2 DFS Traversierungen erfordert.

Um zu überprüfen, ob jeder Knoten beiden Pfade hat und von jedem anderen Knoten in einem Graphen:

1. DFS / BFS von allen Knoten:

Tarjan Algorithmus jeden Knoten setzt eine Tiefe d[i] hat. Zunächst muss die Wurzel die kleinste Tiefe. Und wir tun, um das Post-Order-DFS-Updates d[i] = min(d[j]) für jeden Nachbarn j von i. Eigentlich BFS arbeitet auch mit der Reduktion Regel d[i] = min(d[j]) hier in Ordnung. 

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

Wenn es ein Weiterleitungspfad von u ist, v dann d[u] <= d[v]. In der SCC, d[v] <= d[u] <= d[v] somit alle Knoten in SCC die gleiche Tiefe haben. Zu sagen, ob ein Graph ein SCC ist, prüfen wir, ob alle Knoten die gleiche d[i] haben.

2. Zwei DFS / BFS aus dem einzelnen Knoten:

Es ist eine vereinfachte Version des Kosaraju Algorithmus . Ausgehend von der Wurzel, überprüfen wir, ob jeder Knoten kann durch DFS / BFS zu erreichen. Dann kehrt die Richtung jeder Kante. Wir überprüfen, ob jeder Knoten wieder aus derselben Wurzel zu erreichen. Siehe C ++ Code .

Sie können die All-Pairs Shortest Path und sehen, ob unendlich .

Tarjan-Algorithmus wurde bereits erwähnt. Aber ich finde in der Regel Kosaraju-Algorithmus einfacher zu folgen, auch wenn es zwei Überquerungen des Graphen benötigt . IIRC, es ist auch ziemlich gut in CLRS erklärt. 

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Eine Möglichkeit, dies zu tun wäre, die Laplace-Matrix für den Graphen zu erzeugen, dann berechnen der Eigenwerte und schließlich die Anzahl der Nullen zählen. Die Grafik ist stark Verbindung, wenn es nur einen Eigenwert Null vorhanden ist.

. Hinweis: Achten Sie auf die etwas andere Methode für die Laplace-Matrix für gerichtete Graphen zu schaffen

Sie können Kosaraju DFS basiert einfachen Algorithmus verwenden, die zwei DFS Querungen von Graphen tut:

Die Idee ist, wenn jeder Knoten von einem Knoten v erreicht werden kann, und jeder Knoten kann v erreichen, dann wird die Graph stark verbunden. In Schritt 2 des Algorithmus, überprüfen wir, ob alle Ecken von v erreichbar sind. In Schritt 4 überprüfen wir, ob alle Ecken v erreichen können (in umgekehrter Diagramm, wenn alle Knoten von v erreichbar sind, dann können alle Ecken v in Original erreichen Grafik).

Algorithmus: 1) Initialisieren Sie alle Ecken als nicht besucht.

2) Führen Sie ein DFS-Traversal von Graphen von einem beliebigen Knoten v zu starten. Wenn die DFS-Traversal nicht alle Knoten nicht besuchen, dann false zurück.

Rückwärts

3) alle Bögen (oder finden transponieren oder umgekehrt von Grafik)

4) Markieren Sie alle Ecken als in umgekehrtem graphen nicht besucht.

5) Führen Sie einen DFS-Traversal reversed Graphen ausgehend von derselben Ecke v (Die gleichen wie Schritt 2). Wenn DFS-Traversal nicht alle Ecken besuchen, dann false zurück. Andernfalls true zurück.

Zeit Komplexität:. Zeit Komplexität der obigen Implementierung ist die gleiche wie Tiefensuche, die O (V + E) ist, wenn der Graph dargestellt wird, mit Adjazenzliste Darstellung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top