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