Trivial O(V^3) Lösung könnte floyd warshal sein, die alle am kürzesten sind Pfad, aber das ist ein Overkill (in Bezug auf die zeitliche Komplexität).
Es kann in O(V+E) gemacht werden.
Anspruch:
Ein DAG ist in einer topologischen Sortierung halb verbunden, für jedes i gibt es eine Kante (vi,vi+1)
Beweis:
Gegeben eine DAG mit topologischer Sortierung v1,v2,...,vn :
Wenn für einige (vi,vi+1) keine Kante i vorhanden ist, dann gibt es auch keinen Pfad (vi+1,vi) (da es sich um eine topologische Art von DAG handelt), und das Diagramm ist nicht semi-verbunden.
Wenn für jede i eine Kante (vi,vi+1) vorhanden ist, dann für jede i,j (ivi- & gt; vi + 1- & gt; ...- & gt; vj-1- & gt; vj und die Graph ist halb verbunden.
Daraus können wir den Algorithmus erhalten:
U eine Menge von SCCs ist. %Code%
Korrektheitsbeweis:
Wenn das Diagramm halb verbunden ist, für ein Paar E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E) , so dass es einen Pfad gibt (v1,v2) - Seien V1, V2 ihre SCCs. Es gibt einen Pfad von V1 nach V2 und somit auch von v1 nach v2, da alle Knoten in V1 und V2 stark verbunden sind.
Wenn der Algorithmus wahr ergeben hat, dann sind für zwei gegebene Knoten v1, v2 - in SCC V1 und V2. Es gibt einen Pfad von V1 nach V2 (ohne Verlust der Allgemeinheit) und somit auch von v1 nach v2.
Als Randnotiz hat auch jeder semi-verbundene Graph eine Wurzel (Vertex v1->...->v2 , die zu allen Vertices führt):
Beweis:
Angenommen, es gibt keine Wurzel. Definieren Sie r (Anzahl der Knoten mit einem Pfad von #(v) = |{u | there is a path from v to u}| zu ihnen).
Wählen Sie v so, dass a .
#(a) = max{#(v) | for all v} ist kein Root, also gibt es einen Knoten a , der keinen Pfad von u zu ihm hat. Da der Graph semi-verbunden ist, bedeutet dies, dass es einen Pfad a gibt. Aber das heißt u->...->a (alle Knoten erreichbar von #(u) >= #(a) + 1 und auch a ).
Widerspruch zur Maximierung von u , also gibt es eine Wurzel.
Amits Lösung beschreibt den effizientesten Ansatz. Ich könnte nur hinzufügen, dass man Schritt 4 ersetzen kann, indem man überprüft, ob es mehr als eine topologische Ordnung von G 'gibt. Wenn ja, dann ist der Graph nicht halb verbunden. Ansonsten ist das Diagramm halb verbunden. Dies kann leicht in Kahns Algorithmus zum Auffinden der topologischen Ordnung eines Graphen integriert werden.
Eine andere weniger effiziente Lösung, die in quadratischer Zeit arbeitet, ist die folgende.
Konstruiere zuerst einen anderen Graphen G *, der die Umkehrung des ursprünglichen Graphen ist. Dann führen Sie für jeden Vertex v von G ein DFS von v in G aus und betrachten die Gruppe erreichbarer Knoten als R_v. Wenn R_v! = V (G), dann führe ein anderes DFS von v in G * aus und lass die Menge erreichbarer Knoten R _v sein. Wenn die Vereinigung von R_v und R _v nicht V (G) ist, dann ist der Graph nicht halb verbunden.