\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

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\):

9 12 
0 2 
1 8
2 0 
2 6
3 2
3 7
4 5 
5 6
6 4 
7 8 
8 4
7

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:

0 -1
1 -1 
2 -1 
3 -1
4 2 
5 3 
6 4 
7 0 
8 1
Ü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
  1. 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.
  2. 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.
  3. Wie müssen Sie den Pseudocode ändern, damit der Algorithmus korrekt ist?