zurück zur Liste

Darstellungen von Graphen

Grafiken entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"

Adjazenzmatrix

Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindung als nxn-Matrix sinnvoll, wobei n = Knotenanzahl |V|. Eine derartige Matrix wird als Adjazenzmatrix bezeichnet.
Gibt es eine Kante von Knoten a zu Knoten b, wird in der Matrix in der a-ten Zeile an der b-ten Stelle ein True bzw. eine 1 eingetragen.

Beispiel eines gerichteten Graphen


Beispiel eines ungerichteten Graphen

Bei ungerichteten Graphen muss eigentlich nur die Hälfte gespeichert werden, da sich die andere Hälfte durch Spiegelung ergibt.

Adjazenzliste

Die Möglichkeit einen Graphen in einer dynamischen Datenstrucktur zu realisieren ist zum Beispiel die Adjazenzliste.
Ein Graph wird dabei durch |V| + 1 verkette Listen dargestellt. Die Basisstruktur bildet die Liste aller Knoten. Für jeden Knoten wird eine Liste der Nachfolger entlnag gerichteter Kanten abgespeichert.

Beispiel eines gerichteten Graphen