Adjazenzmatrix und Adjazenzliste
Du weißt einfach nicht wie du darstellen sollst, zwischen welchen Knoten Kanten existieren und dann auch noch zu welchen Kosten? Das erklären wir dir jetzt!
Inhaltsübersicht
Adjazenzmatrix
Das Wort Adjazenz bedeutet so viel wie Nachbarschaft. Es geht also um die Beziehung der Knoten eines Graphen zueinander.
Bei der Adjazenzmatrix handelt es sich um eine 
Matrix, aus der du ablesen kannst, ob du von einem Knoten
zu einem anderen Knoten gehen kannst und welche Kosten
damit verbunden sind. N ist hierbei die Anzahl der Knoten, die der Graph enthält.
Beispiel ungerichteter Graph
Stell dir vor du weißt von einem Graphen nur, dass er aus den Knoten A, B, C und D besteht. Doch woher willst du jetzt wissen, ob du von Knoten A zu Knoten D gehen darfst? Richtig, aus der Adjazenzmatrix. Zum Verständnis: diese Matrix hat denselben Informationsgehalt wie dieser einfache Graph:
Falls dir die Grundlagen der Graphentheorie nicht bekannt sind, solltest du dir zuerst unser Video anschauen, in dem wir dir die Basics erklären!
Eine 1 in einer Zelle bedeutet hier, dass eine Kante zwischen zwei Knoten existiert. Eine 0 bedeutet, dass zwei Knoten nicht miteinander verbunden sind. Die Matrix ist bei einem ungerichteten Graph ober und unterhalb der Diagonale symmetrisch, da beispielsweise die Kante von A nach B auch in die andere Richtung benutzt werden kann.
Da bei der Adjazenzmatrix die Anzahl der Kanten keine Rolle für die Größe der Matrix spielt, eignet sie sich anders als die Inzidenzmatrix für Graphen mit vielen Kanten.
Achtung: Bei einem gewichteten Graphen wird anstatt Einsen das jeweilige Gewicht der Kante in die Matrix geschrieben!
Beispiel gerichteter Graph
Schauen wir uns das an einem gerichteten Graphen mit Kantengewichten an.
Zuerst erstellen wir uns eine leere Matrix für alle Knoten. Wir sehen, dass kein Knoten eine Kante zu sich selbst hat, also können wir in die jeweiligen Zellen eine 0 eintragen.
Beginnen wir jetzt bei Knoten A. Wir sehen, dass von A zu B eine Kante mit einem Kantengewicht von 25 verläuft. Dieses Kantengewicht tragen wir in die zugehörige Zelle. Anders herum verläuft keine Kante vom Knoten B zu A, also können wir in diese Zelle eine 0 eintragen.
Wiederholen wir das für alle Knoten, erhalten wir dieses Ergebnis:
Adjazenzliste
Zum Schluss schauen wir uns noch kurz Adjazenzlisten an. Hierbei werden einfach für jeden Knoten beim ungerichteten Graphen alle Nachbarn und beim gerichteten Graphen alle Nachfolger in einer Liste gespeichert. Versuchen wir das für einen einfachen Graphen.
Wir schreiben uns für jeden Knoten eine Liste mit seinen Nachbarn. Knoten A ist beispielsweise mit den Knoten B und C verbunden. Das schreiben wir uns auf.
Wiederholen wir das für alle Knoten erhalten wir unsere Liste.
Wie du siehst ist diese Liste auf einen Blick deutlich einfacher zu lesen als die Matrix. Speziell im Bereich der Informatik muss aber beachtet werden, dass sie oft mit Datenstrukturen wie verketteten Listen realisiert werden. Damit ist das Überprüfen, ob eine Kante zwischen Knoten vorhanden ist, mit Adjazenzlisten oft aufwendiger.
Perfekt! Jetzt weißt du, wie du in Zukunft Graphen sinnvoll und einheitlich darstellen kannst.