6.2 Zusammenhang, Kreise finden, Tiefensuche, Breitensuche

In diesem Teilkapitel sind alle Graphen ungerichtet.

Definition 6.2.1 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

G

gibt.

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

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

Algorithmisches Problem 6.2.2 ( $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). Dafür stellen wir uns vor, wir stünden auf dem Knoten $s$ und wollten nun den Graphen systematisch erkunden. Wie Theseus im Labyrinth ziehen wir einen Faden hinter uns her, um uns zu merken, woher wir gekommen sind; zusätzlich führen wir noch ein Stück Kreide mit, mit dem wir besuchte Knoten markieren. In jedem Schritt gehen wir zu einem beliebigen benachbarten Knoten, der noch unmarkiert ist; sind alle Nachbarn markiert, gehen wir mit Hilfe des Fadens einen Schritt zurück und suchen dort nach unmarkierten Nachbarknoten weiter; sobald wir wieder am Anfangsknoten $s$ sind und feststellen, dass alle Nachbarn markiert sind, sind wir fertig: alle von $s$ aus erreichbaren Knoten tragen nun eine Markierung.

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

Theorem 6.2.3 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.

Datenformat. Das Programm UndirectedConnectivity.java liest die Daten in folgendem Format ein:

n m       # n ist die Anzahl der Knoten, m ist die Anzahl der Kanten                                
u_1 v_1   # die erste Kante; die Reihenfolge spielt keine Rolle; v_1 u_1 funktioniert also auch
u_2 v_2   # die zweite Kante
...
u_m v_m   # die letzte Kante
s         # Startknoten, an welchem die Tiefensuche starten soll

Übungsaufgabe 6.2.2 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.

Tip. Nutzen Sie mein im Moment sehr rudimentäres Zeichenprogramm, um Graphen zu zeichnen und in das oben beschriebene Format zu exportieren:

Übungsaufgabe 6.2.3 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 6.2.4 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 6.2.4 Sie

G = (V, E)

ein Graph und

u \in V

ein Knoten. Die Zusammenhangskomponente von $u$ ist die Teilmenge

C C_{G} (u) := {x \in V | \exists ein Pfad von u nach x}

Die Menge aller Zusammenhangskomponenten von

G

ist die Menge

C C (G) := {C C_{G} (u) | u \in V} .

Als Beispiel betrachten wir diesen Graphen.

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

Übungsaufgabe 6.2.5 Erweitern Sie die Tiefensuche, so dass nun die Menge

C C (G)

bestimmt wird.

Input. Ein Graph im obigen Format.

Output. $n$ Zeilen, von denen die $i$ -te aus zwei Zahlen $i$ und $c_{i}$ besteht, durch ein Leerzeichen getrennt, wobei $c_{i}$ der kleinste Knoten ist, der in $C C_{G} (i)$ liegt. Die Numerierung beginnt bei 0.

Beispiel-Input (für den Graphen ):

Beispiel-Output:

Übungsaufgabe 6.2.6 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.

Tiefensuche ohne Rekursion

Viele Laufzeitumgebungen stürzen ab, wenn der Rekursionsstack eine gewisse Höhe überschreitet.

Demo. Kompilieren Sie das Programm LongPath.java und führen es aus. Es erzeugt einen Pfad mit $n$ Knoten und lässt dann rekursive Tiefensuche darauf laufen. Ab einer gewissen Knotenzahl stürzt es ab.

Alternativ können wir den Rekursionsstack "selbst" unterhalten, also als Stack-Datenstruktur, die dann aber auf dem Laufzeit-Heap liegt. Der Pseudocode sieht dann so aus:

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

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 (queue.size() > 0):
        u = queue.pop()
        for v in neighbors(u): 
            if (!visited[v]):
                visited[v] = true 
                queue.push(v)
    return visited

Lemma 6.2.5 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 6.2.7 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

Mit etwas zusätzlicher "Buchhaltung" können wir uns merken, über welche Pfade ein Knoten erreicht worden ist:

Übungsaufgabe 6.2.8 Passen Sie meine Implementierung der Breitensuche so an, dass nach Eingabe des Graphen und zweier Knoten $s$ und $t$ ein kürzester Pfad von $s$ nach $t$ ausgegeben wird.