Die Adjazenzmatrix bildet einen Graphen mit n Knoten als n×n-Tabelle ab. Der Eintrag in Zeile i und Spalte j sagt, ob eine Kante von Knoten i zu Knoten j führt: 1 für „ja“, 0 für „nein“ — bei gewichteten Graphen steht dort das Kantengewicht.
Beispiel
Vier Knoten A, B, C, D mit den Kanten AB, AC, BD und CD ergeben folgende Matrix:
A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]Die Matrix ist symmetrisch, weil der Graph ungerichtet ist: Eine Kante von A nach B existiert genau dann, wenn auch eine von B nach A existiert. Bei gerichteten Graphen entfällt die Symmetrie.
Eigenschaften
- Kantenabfrage: O(1) — der Zugriff auf Matrix[i][j] beantwortet die Frage sofort.
- Platzbedarf: O(n²) — auch ein Graph mit nur wenigen Kanten belegt die komplette Tabelle.
- Dichte Graphen: sind hier im Vorteil; bei vielen Kanten ist die Matrix oft kompakter als eine Adjazenzliste mit ihren Verweiskosten.
Im Vergleich zur Adjazenzliste
Die Adjazenzliste benötigt nur O(V + E) Speicher und liefert die Nachbarn eines Knotens schneller; die Adjazenzmatrix punktet bei der Kantenabfrage und bei dichten Graphen. Der Dijkstra-Algorithmus lässt sich mit beiden Darstellungen implementieren: mit der Matrix erreicht die einfache Variante O(V²), mit einer Heap-gestützten Adjazenzliste ist sie schneller.