Eine Zusammenhangskomponente (englisch connected component) ist die größte Teilmenge von Knoten eines Graphen, in der jeder Knoten jeden anderen über Pfade erreichen kann. Man kann sich die Komponenten als Inseln vorstellen: Innerhalb einer Insel kommt man überall hin, zwischen den Inseln gibt es keine Verbindung.
Komponenten in ungerichteten Graphen
Ein ungerichteter Graph zerfällt immer in eine oder mehrere Zusammenhangskomponenten. Ist der ganze Graph eine einzige Komponente, nennt man ihn zusammenhängend. Die Kanten bestimmen dabei, welche Knoten zusammengehören – der Grad eines Knotens allein reicht zur Einordnung nicht aus.
Starke Zusammenhangskomponenten in gerichteten Graphen
Bei gerichteten Graphen unterscheidet man zusätzlich zwischen schwach und stark zusammenhängend. Eine starke Zusammenhangskomponente (SCC) verlangt, dass zwischen je zwei Knoten Pfade in beide Richtungen existieren. Rings um eine SCC kann es Zyklen geben, und die topologische Sortierung arbeitet nur in azyklischen Graphen – starke Komponenten müssen zuerst kontrahiert werden, um einen azyklischen Graphen zu erhalten.
Komponenten finden
- Tiefensuche und Breitensuche: Ein Durchlauf der Tiefensuche oder Breitensuche entdeckt genau eine Komponente; jeder neue Startknoten nach einem abgeschlossenen Durchlauf gehört zur nächsten Komponente. Der Aufwand ist linear O(V + E) in der Zahl der Knoten und Kanten – gemessen in der Big-O-Notation.
- Union-Find: Die Union-Find-Struktur verwaltet Komponenten dynamisch, während Kanten hinzugefügt werden – ideal für wachsende Netze.
- Tarjan und Kosaraju: Spezial-Algorithmen für starke Zusammenhangskomponenten in gerichteten Graphen.
Die Darstellung des Graphen – als Adjazenzliste oder Adjazenzmatrix – beeinflusst, wie schnell die Komponentenanalyse läuft; beide speichern die Kanten, über die die Komponenten überhaupt erst entstehen.
Wozu man Komponenten braucht
- Netzwerkanalyse: Ausfallsichere Netze sollen keine isolierten Inseln haben – jede Komponente ist ein Risikobereich.
- Soziale Netzwerke: Freundesgruppen und Communities sind natürliche Zusammenhangskomponenten.
- Routenplanung: Der Dijkstra-Algorithmus und der Bellman-Ford-Algorithmus können nur innerhalb einer Komponente kürzeste Wege finden – unerreichbare Ziele liegen per Definition in anderen Komponenten.
- Netzwerkausbau: Der Minimaler Spannbaum verbindet eine Komponente mit minimalen Kosten; mehrere Komponenten werden durch neue Kanten verschmolzen.
Abgrenzung
Die Zusammenhangskomponente ist keine eigene Datenstruktur, sondern eine Eigenschaft des Graphen: Der Graph liefert die Struktur, die Komponentenanalyse beschreibt, welche Teile zusammenhängen. Knoten und Kanten sind die Bausteine, die Traversierung das Mittel, die Komponenten zu entdecken.