73 lines
1.3 KiB
Markdown
73 lines
1.3 KiB
Markdown
|
---
|
||
|
|
title: Tiefensuche
|
||
|
|
date: 2018-11-14
|
||
|
|
---
|
||
|
|
|
||
|
|
Andere Art einen Spannbaum zu finden.
|
||
|
|
|
||
|
|
**Idee**: Starte bei einem Startknoten und laufe im Graphen soweit wie möglich
|
||
|
|
(ohne Knotenwiederholung).
|
||
|
|
|
||
|
|
Zwei Änderungen gegenüber Breitensuche:
|
||
|
|
|
||
|
|
i) Stack statt Queue
|
||
|
|
i) Wir bearbeiten zuerst nur einen Nachbarn
|
||
|
|
|
||
|
|
|
||
|
|
# Algorithmus (Tiefensuche)
|
||
|
|
|
||
|
|
**Eingabe**: $G=(V,E)$ und $s \in V$
|
||
|
|
|
||
|
|
i) $pred[v] = NIL, \forall v \in V$
|
||
|
|
i) $S \leftarrow new Stack()$
|
||
|
|
i) $S.push(s)$
|
||
|
|
i) `while (!`$S.isEmpty()$`)`
|
||
|
|
|
||
|
|
a) $v \leftarrow S.pop()$
|
||
|
|
a) falls $\exists u \in \Gamma(v) \setminus \{s\}, pred[u] == NIL$
|
||
|
|
|
||
|
|
* $pred[u] = v$
|
||
|
|
* $S.push(v)$
|
||
|
|
* $S.push(u)$
|
||
|
|
|
||
|
|
|
||
|
|
**Ausgabe**: $pred[v], \forall v \in V$
|
||
|
|
|
||
|
|
|
||
|
|
**Beispiel**: Tiefensuche (Startknoten $A$)
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
| $v$ | A | B | C | D | E | F |
|
||
|
|
| --- | --- | --- | --- | --- | --- | --- |
|
||
|
|
| $pred[v]$ | $\emptyset$ | C | A | B | D | E |
|
||
|
|
|
||
|
|
| Stack |
|
||
|
|
| --- |
|
||
|
|
| ~~F~~ |
|
||
|
|
| ~~E~~ |
|
||
|
|
| ~~E~~ |
|
||
|
|
| ~~D~~ |
|
||
|
|
| ~~D~~ |
|
||
|
|
| ~~B~~ |
|
||
|
|
| ~~B~~ |
|
||
|
|
| ~~C~~ |
|
||
|
|
| ~~C~~ |
|
||
|
|
| ~~A~~ |
|
||
|
|
| ~~A~~ |
|
||
|
|
| S |
|
||
|
|
|
||
|
|
|
||
|
|
# Satz (Spannbaum Erzeugung)
|
||
|
|
|
||
|
|
Bei Eingabe eines zusammenhängenden Graphen $G=(V,E)$ liefert Algorithmus
|
||
|
|
Tiefensuche einen Spannbaum $T=(V,E)$ mit $E' = \{ \{u,pred[u]\} | u \in V
|
||
|
|
\setminus \{s\} \}$ von $G$ in Laufzeit $O(|V| + |E|)$
|
||
|
|
|
||
|
|
# Beweis
|
||
|
|
|
||
|
|
Analog zur Breitensuche
|
||
|
|
|
||
|
|
|