6. Graphen

6.3 Gerichtete Graphen

Dies ist ein gerichteter Graph:

Definition. Ein gerichteter Graph ist ein Paar \((V,E)\) mit \(E \subseteq V \times V\).

Die Definitionen von Pfad, Kreis, Kantenzug und geschlossenem Kantenzug müssen jetzt so angepasst werden, dass die Richtung der Kanten beachtet wird.

Die Menge \(V \times V\) ist die Menge aller geordneten Paare. Der obige Graph ist also \(G = (V,E)\) mit \(V = \{a,b,c,d,e,f,g,h,i\}\) und \(E = \{(a,d), (b,i), (c,a), (c,g), (d,c), (d,h), (e,f), (f,g), (g,e), (h,i), (i,h), (i,e)\}\) Die Darstellung als Adjazenzmatrix oder mit Adjazenzlisten sowie die Codierung im "ICPC"-Format bleibt im Prinzip gleich. Eine Zeile u v im ICPC-Format bedeutet dann eine gerichtete Kante \(u,v\) und eben nicht die in die Gegenrichtung \(v,u\); falls die auch im Graph sein sollte, müsste sie separat in einer anderen Zeile aufgeführt werden: v u. Mein Java-Code ist ähnlich (Digraph.java), allerdings speichere ich für jeden Knoten eine Liste hinausgehender Kanten und eine Liste hereinkommender Kanten: outEdges und inEdges.

Implementierung für Graphen mit Knotennamen. Ich empfehle Ihnen im folgenden, meine Implementierung 02-named-graphs.zip zu verwenden. Da können Sie den Knoten explizit Namen geben, was die Arbeit deutlich erleichtert.

Übungsaufgabe Passen Sie Ihre Implementierung von Breitensuche so an, dass es für jeden Knoten \(u\) die Distanz \(\dist(s,u)\) ausgibt.

Input. Ein Graph im ICPC-Format, gefolgt von einer Zeile, die ein einzelnes int enthält: den Startknoten \(s\). Beispiel-Input für den obigen Gerichteten Graphen und Startknoten \(h\), mit Codierung \(a = 0, b = 1, \dots, i = 8\):

Output. Eine Folge von \(n\) Zeilen. Die \(i\)-te Zeile enthält zwei durch ein Leerzeichen getrennte Werte: \(i\) und \(\dist(s,i)\). Solle es keinen Pfad von \(s\) nach \(i\) geben, so geben Sie \(\dist(s,i)\) mit \(-1\) an. Beispiel-Output:

Übungsaufgabe

Betrachten Sie folgenden DFS-basierten Algorithmus, der entscheiden will, ob ein gerichteter Graphen einen Kreis enthält:

def containsCycle(graph):
    alreadyVisited = [all-false-array]
    for u in graph.vertices:
        if !alreadyVisited[u] and cycleReachableFrom(u, alreadyVisited):
            return True 
    return False 

def cycleReachableFrom(u, alreadyVisited):
    if alreadyVisited[u]: return True 
    alreadyVisited[u] = True 
    for v in graph.neighbors(u):
        if (cycleReachableFrom(v, alreadyVisited)):
            return True 
    return False

Zeigen Sie, dass der Algorithmus fehlerhaft ist: zeichnen Sie einen azyklischen gerichteten Graphen, für den containsCycle mit True antwortet. Im Prinzip führt er von jedem Knoten aus Tiefensuche aus und meldet Kreis gefunden!, sobald er einem bereits zuvor besuchten Knoten begegnet.
Zeigen Sie, dass der Algorithmus sich nicht "in der anderen Richtung" irren kann. Das heißt, zeigen Sie, dass, falls \(G\) einen Kreis enthält, dann der Algorithmus auf jeden Fall True zurückliefert.
Wie müssen Sie den Pseudocode ändern, damit der Algorithmus korrekt ist?

Übungsaufgabe Wir definieren einen Graphen auf der Liste englischer Wörter in englishVocabulary.txt. Zwei Wörter sind durch eine Kante verbunden, wenn sie sich nur in einem Buchstaben unterscheiden, wie beispielsweise live und love. Dies ist ein ungerichteter Graph.

Schreiben Sie ein Programm, das englishVocabulary.txt oder eine vergleichbare Datei einliest, den obigen "Buchstabenaustauschgraphen" baut, dann den User auffordert, zwei Wörter einzugeben (beispielsweise dead und live) und versucht, einen Pfad vom einen zum anderen zu finden:

java FindVocabularyPath englishVocabulary.txt                            
[enter first word:] dead
[enter second word:] live
path found:
// verrate ich Ihnen an dieser Stelle nicht

Übungsaufgabe Ändern Sie den Code aus der vorherigen Aufgabe so ab, dass Ihr Programm die gesamte Zusammenhangskomponente eines Wortes findet, also

java FindVocabularyPath englishVocabulary.txt                            
[enter word:] dead 
read
deal 
deaf 
leaf 
lean 
...