---
title: Zusammenhangskomponenten
date: 2018-11-14
---

Breitensuche kann genutzt werden, um die Zusammenhangskomponenten eines Graphen
zu berechnen.

# Algorithmus (vollständige Breitensuche)

**Eingabe**: $G=(V,E)$ als Adjazenzliste

i) setze $i = 1$

i) `while(V `$\neq \emptyset$`)` do

    a) wähle $s \leftarrow V$ beliebig
    a) $d,p \leftarrow BREITENSUCHE(G,s)$
    a) $v_i = \{ v \in V | d[v] \neq \infty \}$
    a) $V' = V \setminus \{v_i\}$
    a) $G = G[V']$
    a) $i \leftarrow i + 1$


**Ausgabe**: (Zusammenhangskomponenten von $G$) $G[V_1], ... G[V_{i-1}]$


# Satz (Laufzeit vollständige Breitensuche)

Vollständige Breitensuche berechnet in Zeit $O(|V| + |E|)$ die
Zusammenhangskomponenten von $G$.

Beweis: klar