6. Graphen

6.2 Zusammenhang, Kreise finden, Tiefensuche, Breitensuche

Definition Ein Graph $G = (V,E)$ heißt zusammenhängend (connected), wenn es für alle $u, v \in V$ einen Pfad von $u$ nach $v$ in $G$ gibt.

Übungsaufgabe Ist der rechte Graph in der obigen Abbildung zusammenhängend oder nicht?

Der erste algorithmische Problem, das wir untersuchen werden, ist Graphenzusammenhang.

Algorithmisches Problem ($s,t$-Graphenzusammenhang, $s,t$-Connectivity). Gegeben ein Graph $G = (V,E)$ und zwei Knoten $s,t \in V$, entscheide, ob es einen Pfad von $s$ nach $t$ gibt.

Wir haben dies als ein Entscheidungsproblem formuliert, also als Ja/Nein-Frage. In der Komplexitätstheorie untersuchen wir vorwiegend solche Entscheidungsprobleme. In der Praxis wollen wir natürlich nicht nur eine Ja/Nein-Antwort, sondern in diesem konkreten Fall auch den Pfad, sollte er denn existieren.

Wir lösen $s,t$-Graphenzusammenhang mit dem Algorithmus Tiefensuche (depth-first search). Hier ist der Pseudocode:

def depthFirstSearch(u):
    if marked[u]: return
    else:
        marked[u] = true 
        for v in neighbors(u):
            depthFirstSearch(v)

Theorem Wenn wir marked als [false, ..., false] initialisieren und depthFirstSearch(u) aufrufen, dann terminiert der Aufruf; nach Terminierung ist marked[v] = true genau dann, wenn es einen Pfad von u nach v gibt.

In Graph.java finden Sie eine einfache Graphen-Klasse. Meine Implementierung von Tiefensuche finden Sie in UndirectedConnectivity.java.

Übungsaufgabe Schreiben Sie test cases für meine Implementierung, nach dem Schema input-01.txt / output-01.txt und vergleichen Sie meinen Output mit dem von Ihnen per Hand geschriebenen "korrekten" Output. (Beachten Sie, dass die Meldungen please enter n: etc. von meinem Programm auf System.err gedruckt werden; wenn Sie java UndirectedConnectivity < input-xx.txt > output-dominik-xx.txt machen, dann wird output-dominik-xx.txt nur den "echten" Output enthalten, nicht aber die Meldungen).

Im folgenden werde ich Sie bitten, aufbauend auf meinem Code (oder auch from scratch, wenn Sie wollen), Algorithmen für mehrere Probleme zu implementieren. Schreiben Sie zu jedem Problem auch ein paar Test-Cases. Alle Algorithmen sollten Laufzeit $O(n+m)$ haben, also lineare Zeit.

Halten Sie sich streng an das Input/Output-Format, damit ich im Zweifelsfall Ihre Lösung per diff mit meiner oder anderen vergleichen kann.

Übungsaufgabe Erweitern Sie meine Datei UndirectedConnectivity, so dass es nicht eine True/False-Tabelle ausgibt, sondern neben dem Startknoten $s$ einen Zielknoten $t$ einliest und dann, wenn es einen Pfad gibt, yes ausgibt, gefolgt von einem Pfad von $s$ nach $t$, oder eben no, falls es keinen gibt. Beispiel:

java UndirectedConnectivity                            
5 6 
4 0 
0 1 
0 2 
1 2 
1 3 
2 3
4 3 
yes
4
0
1
3

Übungsaufgabe Schreiben Sie, gerne basierend auf meinem Code, ein Programm Cyclicity, das testet, ob der gegebene Graph einen Kreis enthält.

Input. Ein Graph in dem oben definierten Format.

Output. Eine einzelne Zeile, die entweder das Wort cyclic oder acyclic enthält.

Definition Sie $G= (V,E)$ ein Graph und $u \in V$ ein Knoten. Die Zusammenhangskomponente von $u$ ist die Teilmenge $$ CC_G(u) := \{x \in V \ | \ \exists \textnormal{ ein Pfad von $u$ nach $x$}\} $$ Die Menge aller Zusammenhangskomponenten von $G$ ist die Menge $$ CC(G) := \{ CC_G(u) \ | \ u \in V \} \ . $$

Als Beispiel betrachten wir diesen Graphen.

Die Zusammenhangskomponente von $1$ wäre also $CC_G(u) = \{1,2,3\}$. Die Menge der Zusammenhangskomponenten von $G$ ist $CC(G) = \{ \{0,4\}, \{5\}, \{1,2,3\}$.

Übungsaufgabe Erweitern Sie die Tiefensuche, so dass nun die Menge $CC(G)$ bestimmt wird.

Input. Ein Graph im obigen Format.

Output. $n$ Zeilen, von denen die $i$-te aus zwei Zahlen $i c_i$ besteht, wobei $c_i$ der kleinste Knoten ist, der in $CC_G(i)$ liegt. Die Numerierung beginnt bei 0.

Beispiel-Input (für Graph ):

Beispiel-Output:

Übungsaufgabe Erweitern Sie die Tiefensuche, so dass nicht nur ein Pfad von $s$ nach $t$ gefunden wird, sondern so ein Pfad auch ausgegebend wird.

Input. Ein Graph $G$ im oben definierten Format; gefolgt von einer Zeile im Format s t, die zwei int enthält.

Output. Falls es keinen Pfad in $G$ von $s$ nach $t$ gibt: das Wort false in einer einzelnen Zeile. Falls es einen Pfad gibt: ein solcher Pfad, beginnend mit $s$ und endend mit $t$, ein Knoten pro Zeile.

Breitensuche: kürzeste Wege finden

Tiefensuche erlaubt uns, zu erkennen, ob es einen Pfad von $s$ nach $t$ gibt; auch, einen solchen zu finden. Oft wollen wir aber den kürzesten. Als Länge eines Pfades bezeichnen wir die Anzahl seiner Kanten. Mit $\dist_G(u,v)$ bezeichnen wir den Abstand zwischen $u$ und $v$, also die Länge eines kürzesten Pfades von $u$ nach $v$. Im folgenden erkläre ich das Prinzip der Breitensuche. Wir halten eine Warteschlange von Knoten, die am Anfang nur $s$ enthält. In jedem Schritt entfernen wir den ersten Knoten $u$ aus der Warteschlange und fügen alle seine Nachbarn ein, außer denen, die bereits einmal in der Warteschlange waren. Wir brauchen also eine Warteschlange queue und ein Array visited, das uns anzeigt, ob ein Knoten bereits einmal in der Warteschlange war.

def breadthFirstSearch(s):
    queue = new Queue();
    visited = [false, ..., false]
    queue.push(s)
    visited[s] = true
    while (active.size() > 0):
        u = queue.pop()
        for v in neighbors(u): 
            if (!visited[v]):
                visited[v] = true 
                queue.push(v)
    return visited

Nachdem breadthFirstSearch terminiert hat, ist visited[u] = true genau dann, wenn es einen Pfad von s nach u gibt. Darüberhinaus gilt: wenn Zeilen 10 und 11 durchlaufen werden, dann gilt $\dist(s,v) = \dist(s,u) + 1$.

Meine Java-Implementierung finden Sie in BreadthFirstSearch.java.

Übungsaufgabe Erweitern Sie meinen Code, sodass nun für jeden Knoten $u$ der Abstand $\dist(s,u)$ ausgegeben wird.

Input. Ein Graph im obigen Format, gefolgt von einer Zeile, die ein einzelnes int enthält: den Knoten $s$. Beispiel:

Output. $n$ Zeilen, die jeweils zwei int enthalten. Die $i$-te enthält die Zahlen $i$ und $\dist(s,i)$. Beispiel:

Solle es keinen Pfad von $s$ nach $i$ geben, so geben Sie $\dist(s,i)$ mit $-1$ an