Adjazenzmatrix

Sei ein Graph. Zwei Knoten heißen adjazent, wenn . Die Adjazenzmatrix des Graphen ist wie folgt definiert:

Die Adjazenzmatrix eines ungerichteten Graphen ist symmetrisch.

Eigenschaften

• Zugriff auf Kanten in Zeit
• Berechnung Knotengrad in Zeit
• Kanten- oder Knotengewichtung kann einfach ergänzt werden
• Quadratischer Speicheraufwand ist ein Nachteil, wenn ein Graph nur wenige Kanten enthält, z.B. nur linear in viele
• Initialisierung und Ausgabe eines Graphen in Zeit

Siehe auch

Matrix, Adjazenzliste