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!
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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.
Adjazenzmatrix und Adjazenzliste — häufigste Fragen
(ausklappen)
Adjazenzmatrix und Adjazenzliste — häufigste Fragen
(ausklappen)-
Was ist ein gerichteter Graph?Ein gerichteter Graph ist ein Graph, bei dem jede Kante eine feste Richtung hat. Du kannst eine Kante also nur in Pfeilrichtung benutzen, zum Beispiel von Knoten A nach Knoten B. Eine Verbindung zurück von B nach A gilt nur dann, wenn es dafür auch eine eigene gerichtete Kante gibt.
-
Was bedeutet adjazent?Adjazent bedeutet in der Graphentheorie, dass zwei Knoten direkte Nachbarn sind. Konkret heißt das: Zwischen den beiden Knoten gibt es eine Kante. Bei einem gerichteten Graphen kann die Adjazenz richtungsabhängig sein, wenn die Kante nur von einem Knoten zum anderen zeigt.
-
Was sind Nachbarschaftslisten?Nachbarschaftslisten sind Listen, in denen du zu jedem Knoten die direkt benachbarten Knoten notierst. Du schreibst also pro Knoten auf, welche Knoten über eine Kante erreichbar sind. Im Unterschied zur Adjazenzmatrix steht hier nicht alles in einer Tabelle, sondern als Sammlung von Listen.
-
Was ist eine gerichtete Adjazenzmatrix?Eine gerichtete Adjazenzmatrix ist eine n×n-Matrix für einen gerichteten Graphen, in der du Kanten mit ihrer Richtung codierst. Die Zeile steht für den Startknoten und die Spalte für den Zielknoten. In der Zelle steht dann 1 (oder das Kantengewicht) falls die Kante existiert, sonst 0.
Graphen verstehen
Adjazenzmatrix und Adjazenzliste gehören zu den Grundformen von Graphen. Wer sich mit Graphen beschäftigt, ordnet Knoten und Kanten in einer klaren Form an. Dabei achtest du auf Richtung, Nachbarn und Kantengewichte. Im Informatikbereich findest du Videos zu gerichteten Graphen, Kantengewichten und mehr.
