---
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$)

![Graph](20181114_3-dfs.png)


| $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