Was ist der effizienteste Weg, um festzustellen, ob ein gerichteter Graph einfach zusammenhängend ist?

Question

Ich arbeite an einer Aufgabe, bei der eines der Probleme darum geht, einen Algorithmus abzuleiten, um zu prüfen, ob ein gerichteter Graph G=(V,E) einfach zusammenhängend ist (es gibt höchstens einen einfachen Pfad von u nach v für alle unterschiedlichen Eckpunkte u, v von V.

Natürlich können Sie es mit Brute-Force überprüfen, was ich gerade mache, aber ich möchte wissen, ob es einen effizienteren Weg gibt.Könnte mir jemand die richtige Richtung weisen?

Answer 1

Hast du es versucht DFS.

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

Komplexität O (V^2), o (v) dfs als keine Wiederholung.

Answer 2

Es gibt eine bessere Antwort auf diese Frage.Sie können das in O(|V|^2) tun.und mit mehr Aufwand können Sie es in linearer Zeit tun.

Zuerst findet man stark zusammenhängende Komponenten von G.In jeder starken Komponente suchen Sie nach diesen Fällen:1) Wenn in dieser Komponente eine Vorwärtskante vorhanden ist, ist es nicht einzeln verbunden, 2) Wenn in dieser Komponente eine Kreuzkante vorhanden ist, ist es nicht einzeln verbunden, 3) Wenn mindestens zwei Rückenkanten in Baum vorhanden sind Scheitelpunkt u, zu den richtigen Vorfahren von u, dann ist es nicht einzeln verbunden.

Dies kann in O(E) erfolgen.(Ich denke, bis auf Fall 3.Ich konnte es nicht gut umsetzen!!).

Wenn keiner der oben genannten Fälle eingetreten ist, sollten Sie prüfen, ob es eine Querkante oder eine Vorwärtskante auf G^SCC gibt (Graph G, wobei starke Komponenten durch einzelne Knoten ersetzt werden), da wir keine Hinterkanten haben, kann dies durch erfolgen Wiederholen von dfs an jedem Scheitelpunkt dieses Diagramms in O(|V|^2).

Answer 3

Lesen Dieses hier. Es erklärt wirklich gut.

Answer 4

Ich bin nicht einverstanden, dass seine Komplexität O (V^2) sein wird, wie in DFS es nicht für jeden Scheitelpunkt, wie es in Einführung in das Algorithmusbuch auch für jeden Scheitelpunkt sitzt, Syntax ist DFS (G). Wir nennen nur DFS für das gesamte Diagramm nicht für einen einzelnen Scheitelpunkt im Gegensatz zu BFS. Hier in diesem Fall müssen wir es also überprüfen, indem wir einmal DFS anrufen. Wenn ein besuchter Scheitelpunkt erneut angetroffen wird, ist das Diagramm nicht nur miteinander verbunden (auf jeden Fall müssen wir es für jede getrennte Komponente aufrufen, aber es bereits im Code enthalten ist ). Die Komplexität wird also O (V+E) sein. Wie hier sollte e = v daher die Komplexität O (V) sein.

Answer 5

Ich habe daran gedacht:1) Führen Sie DFS von einem beliebigen Scheitelpunkt aus aus. Wenn alle Scheitelpunkte im DFS ohne vordere Kanten abgedeckt sind (es kann kein Kreuz geben, da sonst nicht alle Scheitelpunkte abgedeckt werden), kann dies ein potenzieller Kandidat sein.

2) Wenn ein Scheitelpunkt (Ebene j), der im DFS gefunden wird, eine Hinterkante zur Ebene i hat, sollte nach ihm kein weiterer Scheitelpunkt gefunden werden, der eine Hinterkante zu einem Scheitelpunkt mit einer Ebene kleiner als j haben sollte und jeder Scheitelpunkt für ihn erreichbar sein sollte root (überprüft mit zweitem DFS).

Dies geschieht in linearer Zeit, wenn dies korrekt ist.

Answer 6

Schauen Sie sich die Definition des einfachen Pfades an. Ein zyklischer Diagramm kann einzeln verbunden werden. DFS Wird nicht arbeiten für A->B, B->A, was einzeln verbunden ist.

Das folgende Papier verwendet eine stark verbundene Komponente, um dies zu lösen.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 7

Führen Sie DFS einmal von jedem Scheitelpunkt aus. Das Diagramm ist nur dann miteinander verbunden, wenn es keine Vorwärtskanten gibt und es keine Kreuzkanten innerhalb einer Komponente gibt.

Komplexität: o (ve)