Benutzer:Hauix/Scratch

Repräsentation von Graphen

Adjazenzlisten

Geeignet für dünn besetzte Graphen.

Für einen Graphen $G=(V,E)$ speichere für jeden Knoten $u\in V$ ein Feld $u.adj$. Für jede Kante $e=(u,v)\in E$ mache einen Eintrag $v$ in der Liste $u.adj$.

Es müssen insgesamt $\left|V\right|$ Felder gespeichert werden. Die Summe aller Feldlängen ist gerade die Anzahl der Kanten $\left|E\right|$ im Graphen $G$.

Bei der Repräsentation gerichteter Graphen kann bei jedem Feldeintrag für eine Kante zusätzlich ihr Gewicht gespeichert werden. Bei der Traversierung des Graphen ermöglicht dies den unmittelbaren Zugriff (in $O(1)$ Schritten) auf das Kantengewicht.

Adjazenzmatrix

Geeignet für dicht besetzte Graphen.

Eine Adjazenzmatrix zu einem Graphen $G=(V,E)$ ist eine $\left|V\right|\times \left|V\right|$ Matrix $A=(a_{i,j})$ mit Boolschen Werten. Ein Matrixeintrag $a_{i,j}$ ist wahr, wenn in dem Graphen $G$ eine Kante $e=(i,j)$ existiert und falsch andernfalls.

Die Adjazenzmatrix hat immer $\left|V\right|^{2}$ Einträge unabhänig von der Anzahl der Kanten im Graphen. Diese Repräsentationsform eignet sich daher vorzugsweise für dicht besetzte Graphen. Der Speicherplatzbedarf pro Kante reduziert sich auf ein einzelnes Bit pro Kante im Gegensatz zu einem ganzen Speicherwort bei der Adjazenzliste.

Bei gewichteten Graphen wird in den Matrixeinträgen das Gewicht der Kante gespeichert, wenn diese existiert, oder sonst der Wert $\infty$.

Elementare Graph-Algorithmen

Breitensuche

Die Breitensuche traversiert alle Knoten eines Graphen, die von einem gegebenen Startknoten $s$ aus erreichbar sind, in einer bestimmten Reihenfolge. Während der Traversierung wird für jeden Knoten $v\in V$ ein Abstandswert $v.d$ berechnet, der die Länge des kürzesten Pfades vom Startknoten $s$ zu einem Knoten $v$ angibt. Für alle Knoten, die nicht vom Startknoten $s$ erreichbar sind, wird dieser Abstandswert als $\infty$ definiert.

Aufwand

Die Breitensuche und das Berechnen des Tiefenwertes für jeden Knoten ist in $O(V+E)$ Schritten möglich.

Tiefensuche

Die Tiefensuche traversiert alle Knoten eines Graphen so, dass zuerst alle Kinder eines Knotens besucht werden, bevor seine Geschwister besucht werden. Dabei werden für jeden Knoten $v$ zwei Werte $v.d$ und $v.f$ berechnet, die den Zeitpunkt festhalten, zu dem der Knoten aufgefunden wurde ($v.d$) und zu dem die Bearbeitung des Knotens abgeschlossen wurde.

Aufwand

Tiefensuche mit der Berechnung der Werte $v.d$ und $v.f$ ist in $O(V+E)$ Schritten möglich.

Topologische Sortierung

Topologische Sortierung berechnet eine Reihenfolge der Knoten $V$ eines azyklischen gerichteten Graphen $G=(V,E)$. Falls es eine Kante $(v_{1},v_{2})\in E$ gibt, dann kommt in der berechneten Reihenfolge der Knoten $v_{1}$ vor dem Knoten $v_{2}$.

Algorithmus

Topologische Sortierung basiert direkt auf dem Algorithmus für Tiefensuche. Während einer Tiefensuche auf dem Graphen $G$ wird ein Knoten $v$ bei Abschluss seiner Bearbeitung an den Anfang einer Liste angehängt. Nach Beendigung der Tiefensuche sind die Knoten von $G$ topologisch sortiert in der Liste gespeichert.

Aufwand

Da es sich um eine minimal modifizierte Tiefensuche handelt, ist der Aufwand ebenfalls $O(V+E)$.

Starke Zusammenhangskomponenten

Eine Teilmenge der Knoten eines gerichteten Graphen $G=(V,E)$ bildet eine starke Zusammenhangskomponente $C\subseteq V$, wenn jeder Knoten $u\in C$ von jedem anderen Knoten $v\in C$ aus erreichbar ist. Durch zweifache Tiefensuche (auf $G$ und $G^{T}$) können die starken Zusammenhangskomponenten eines Graphen $G$ gefunden werden. (Siehe auch: Zusammenhang von Graphen).

Aufwand

Wie Tiefensuche: $O(V+E).$