Eingabe (Input): Ein gerichteter oder ungerichteter Graph $G= (V,E)$ und ein Start-Knoten $s\in V$
Ziel: Identifiziere die Knoten aus $V$, die von $s$ aus in $G$ erreichbar sind.
Man unterscheidet zwei fundamentale Suchstrategien
GenericSearch¶Input: Graph $G=(V,E)$ and a vertex $s \in V$
Postcondition: a vertex is reachable from $s$ if and only if it is marked as "explored"
mark $s$ as explored, all other vertices as unexplored
while there is an edge $(v,w) \in E$ with $v$ explored and $w$ unexplored do
choose some edge $(v,w)$// underspecified
mark $w$ as explored
Nach Abschluss des generischen Graphsuchalgorithmus ist ein Vertex $v \in V$ genau dann als erkundet (explored) markiert, wenn und nur wenn (iff) mindestens ein Pfad von $s$ nach $v$ existiert.
Dies sollte intuitiv klar sein. Für einen Beweis siehe [TR-AI-p2].
Im generischen Graphsuchalgorithmus wird bei jedem Schritt eine Kante zwischen einem bereits erkundeten (explored) Knoten und einem noch nicht-erkundeten (unexplored) Knoten ausgewählt. Die Kanten zwischen den erkundeten und den nicht-erkundeten Kanten werden als Grenz(kanten) (frontier) bezeichnet.
Für die Art und Weise die Grenzkanten für die weitere Erkundung auszuwählen sind die beiden wichtigten Strategien:
Bei der Breitensuche werden erst alle Knoten einer Schicht vor den Knoten der nächsten Schicht erkundet.
Was ist für einen ungerichteten Graphen mit $n \geq 2$ die minimale und maximale Anzahl der Schichten?
BFS¶Input: Graph $G=(V,E)$ in adjacency-list representation, and a vertex $s \in V$
Postcondition: A vertex is reachable from $s$ if and only if it is marked as "explored".
1mark $s$ as explored, all other vertices as unexplored
2$Q :=$ a queue data structure, initialized with $s$
3while $Q$ is not empty do
4remove (dequeue) the vertex from the front of $Q$, call it $v$
5for each edge $(v, w)$ in $v$'s adjacency list do
6if $w$ is unexplored then
7mark $w$ as explored
8add $w$ to the end of $Q$ (enqueue)
Theorem 8.2 (Eigenschaften von BFS): Für jeden ungerichteten oder gerichteten Graphen $G=(V, E)$ in Adjazenzlistenrepräsentation und für jeden Startknoten $s \in V$ gilt:
Nach Beendigung von BFS ist ein Knoten $v \in V$ genau dann als erkundet markiert, wenn und nur wenn (iff) es mindestens einen Pfad von $s$ nach $v$ gibt.
Die Laufzeit von BFS ist $O(m+n)$.
Die Laufzeit der Zeilen 2-8 des Pseudocodes ist $O(m_s+n_s)$ mit $n_s$ bzw. $m_s$ der Anzahl der Knoten bzw. Kanten, die von $S$ erreichbar sind.
1 ist $O(n)$: Initialisierung einer Liste/Array mit Länge $n$2 ist $=O(1)$3 geht über $n_S$ Knoten, d.h. 3 und 4 ist $O(n_S)$5 (und somit auch Zeile 6) geht über $2*m_S$ (ungerichteter Graph) bzw. $m_S$ (gerichteter Graph) Kanten unabhängig vom äußeren Loop.7 und 8 wird $n_S$-mal ausgeführt.Daraus folgt direkt 3. des Theorems 8.2 und somit auch 2. des Theorems.
Punkt 1. des Theorems folgt aus der Korrektheit von GenericSearch.
Ein Algorithmus zur Berechnung der kürzesten Wege kann mit BFS direkt abgeleitet werden, wenn man bedenkt, dass der Schichtindex der gewünschten Information entspricht.
Augmented BFS¶Input: Graph $G=(V,E)$ in adjacency-list representation, and a vertex $s \in V$
Postcondition: for every vertex $v \in V$, the value $l(v)$ equals to the true shortest path dist$(s,v)$
mark $s$ as explored, all other vertices as unexplored
$l(s) := 0, l(v):= \infty$ for every $v\neq s$
$Q :=$ a queue data structure, initialized with $s$
while $Q$ is not empty do
remove the vertex from the front of Q, call it $v$
for each edge $(v, w)$ in $v$'s adjacency list do
if $w$ is unexplored then
mark $w$ as explored
$l(w) := l(v)+1$
add $w$ to the end of $Q$
Eine verbundene Komponente ist eine Untermenge $S$ der Knoten von $V$, d.h. $S \subseteq V$, mit der Eigenschaft, dass von jedem Knoten in $S$ ein Weg (path) zu jedem anderen Knoten in $S$ existiert.
Graphensuche kann zur Identifikation der verbundenen Komponenten verwendet werden. Es muss lediglich eine äußere Schleife hinzugefügt werden, um über alle Knoten zu iterieren. Dann hat man für jede verbundene Komponente einen Startknoten.
Input: Ein ungerichteter Graph $G=(V,E)$ und ein Startknoten $s \in V$
Ziel: Identifiziere die verbundenen Komponenten von $G$
Was ist die minimale und maximale Anzahl der verbundenen Komponenten, die ein Graph mit $n$ Knoten und $m$ Kanten haben kann.
Lösung:
UCC¶Input: undirected Graph $G=(V,E)$ in adjacency-list representation with $V = \{1,2,3,\dots, n \}$
Postcondition: for every vertex $v, u \in V$, $cc(u)=cc(v)$ if and only if $u$ and $c$ are in the same connected component.
mark all vertices as unexplored
$numCC := 0$
for $i := 1$ to $n$ do\\ try all vertices
if $i$ is unexplored then\\ avoid redundancy
$numCC := numCC + 1$\\ new component
\\ call BFS starting at i
$Q :=$ a queue data structure, initialized with $i$
while $Q$ is not empty do
remove the vertex from the front of $Q$, call it $v$
$cc(v) := numCC$
for each edge $(v, w)$ in $v$'s adjacency list do
if $w$ is unexplored then
mark $w$ as explored
add $w$ to the end of $Q$
DFS (Iterative Implementation)¶Input: Graph $G=(V,E)$ in adjacency-list representation, and a vertex $s \in V$
Postcondition: a vertex is reachable from $s$ if and only if it is marked as "explored"
mark all vertices as unexplored
$S := a$ stack data structure, initialized with $s$
while $S$ is not empty do
remove ("pop") the vertex $v$ from the front of $S$
if $v$ is unexplored then
mark $v$ as explored
for each edge $(v, w)$ in $v$'s adjacency list do
add ("push") $w$ to the end of $S$
DFS (Rekursive Implementation)¶Input: Graph $G=(V,E)$ in adjacency-list representation, and a vertex $s \in V$
Postcondition: a vertex is reachable from $s$ if and only if it is marked as explored
// all vertices unexplored before outer call
mark $s$ as explored
for each edge $(s,v)$ in $s$'s adjacency list do
if $v$ is unexplored then
DFS$(G,v)$
Theorem (Eigenschaften von DFS): Für jeden ungerichteten oder gerichteten Graphen $G=(V, E)$ in Adjazenzlistenrepräsentation und für jeden Startknoten $s \in V$ gilt:
Nach Beendigung von DFS ist ein Knoten $v \in V$ genau dann als erkundet markiert, wenn und nur wenn (iff) es einen Pfad von $s$ nach $v$ gibt.
Die Laufzeit von DFS ist $O(m+n)$ mit $m=|E|$ und $n=|V|$.
DFS wird jede Kante maximal zweimal (zweimal bei ungerichteten Graphen) "durchlaufen". Stack-push/pop
ist in $O(1) \Rightarrow O(m)$. Initialisierung aller Knoten als unexplored ist $O(n)$.D.h. es ist auch (wie bei BFS) $O(m_s+n_s)$ möglich, wenn nur explored gekennzeichnet wird.
BFS.UCC-Algorithmus Breitensuche durch Tiefensuche ersetzt werden.Die Funktion $f(.)$ ordnet somit die Knoten in eine Reihenfolge. Alle Knoten von $G$ werden durch die Kanten so verbunden, dass eine Kante immer von einem Knoten mit niedriger Ordnung zu einem Knoten mit höherer Ordnung zeigt.
Reihenfolgebedingungen (precedence constraints) wie z.B.
Abhängigkeiten (Erfüllungen von Voraussetzungen)
Gegeben sei $G = (V,E)$ mit
Wieviele unterschiedliche topologische Ordnungen gibt es für $G$?
Antwort: 2
Jeder DAG hat eine topologische Ordnung.
Jeder DAG hat mindestens einen Quellknoten (source).
Ein Quellknoten ist ein Knoten ohne eingehende Kanten.
Beweisidee von 8.7: Folgt man ausgehend von jedem beliebigen Knoten Wege rückwärts (vom Kopf zum Schwanz der Kanten), stößt man auf einen Quellknoten. Sonst würde man einen Zyklus erkennen, d.h. der Graph wäre kein DAG.
Beweis von 8.6:
Dieses Vorgehen erzeugt eine korrekte topologische Ordnung, da der Graph immer nur um Knoten ohne eingehende Kanten reduziert wird.
Bei der Reduktion eines DAG $G$ zu einem neuen Graphen $G'$ ist $G'$ auch immer ein DAG, da dabei keine Zyklen hinzugefügt werden (können).
Input: Ein gerichteter Graph $G=(V,E)$.
Output: Eine topologische Ordnung der Knoten von $G$.
Ein Algorithmus kann nach dem Vorgehen in den Beweisen von 8.6 und 8.7 entwickelt werden. Wenn in jeder Iteration/Rekursion eine $O(n)$ Subroutine für das Finden eines Quellknotens verwendet wird, hat dies Zeitkomplexität $O(n^2)$. Bei Nutzung einer Queue erhält man Kahns-Algorithmus. Den wir hier nicht weiter betrachten.
Für dichte Graphen mit $m\in\Theta(n^2)$ ist ein solcher Algorithmus linear in der Anzahl der Kanten $m$. Für dünnbesetzte Graphen gilt dies nicht, da bei diesen $n^2$ viel größer als $m$ ist.
Mit DFS kann eine topologische Ordnung für DAGs erzeugt werden. Dabei wird mit einer äußeren Schleife (in der Subroutine TopoSort) über alle Knoten sichergestellt, dass alle Knoten einen $f$-Wert erhalten.
TopoSort¶Input: directed acyclic graph $G=(V,E)$ in adjacency-list representation
Postcondition: the $f$-values of vertices constitute a topological ordering of $G$
mark all vertices as unexplored
$curLabel$ := $|V|$
for each vertex $v \in V$ do
if $v$ is unexplored then
DFS-Topo$(G,v)$
DFS-Topo (Rekursive Implementation)¶Input: Graph $G=(V,E)$ in adjacency-list representation, and a vertex $s \in V$
Postcondition: every vertex $v$ reachable from $s$ is marked as "explored" and has an assigned $f$-value
mark $s$ as explored
for each edge $(s,v)$ in $s$'s adjacency list do
if $v$ is unexplored then
DFS-Topo$(G,v)$
elif
Cycle-Error Handling
$f(s)$ := $curLabel$
$curLabel := curLabel - 1$
Was passiert, wenn der Algorithmus DFS-Topo auf einen gerichteten Graphen mit Zyklen
angewandt wird?
Antwort: 4.
Für jeden azyklischen Graphen $G =(V,E)$
DFS-Topo gibt eine korrekte topologische Ordnung
für die $f$-Werte aller Knoten.DFS-Topo ist $O(n+m)$ mit $m=|E|$ und $n=|V|$zu 2.
Der Algorithmus durchläuft jede Kante nur einmal (for each edge in DFS-Topo)
bzw. jeden Knoten (for each vertex $v \in V$ in TopoSort) unäbhängig voneinander.
Das impliziert eine Gesamtlaufzeit von $O(n+m)$
zu 1.
Im Algorithmus folgen die Zeilen
$f(s)$ := $curLabel$
$curLabel := curLabel - 1$
aufeinander, daher haben alle Knoten unterschiediche Labels/$f$-Werte.
Für zwei Knoten $v$ und $w$, die mit einer Kante $(v,w)$ verbunden sind, muss gelten $f(v)<f(w)$.
Zwei Fälle: