Theoretische Informatik

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.

Adjazenzmatrix: Nachbarschaft von Knoten
direkt ins Video springen
Adjazenzmatrix: Beziehung von Knoten zueinander

Bei der Adjazenzmatrix handelt es sich um eine n \times n 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:

Adjazenzmatrix: ungerichteter Graph
direkt ins Video springen
Adjazenzmatrix für einen ungerichteten Graphen

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:

Adjazenzmatrix und gerichtete Graphen
direkt ins Video springen
Adjazenzmatrix für einen gerichteten Graph

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.

Erstellen einer Adjazenzliste
direkt ins Video springen
Beispiel für eine Adjazenzliste

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

Perfekt! Jetzt weißt du, wie du in Zukunft Graphen sinnvoll und einheitlich darstellen kannst.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.