Graphen bestehen aus einer Menge von Knoten und einer Menge von Kanten (zwischen den Knoten). Dh. theoretisch lassen sich Graphen folgendermaßen darstellen:

G=(V,E)
V Menge der Knoten
E = VxV , Menge der Kanten (karthesisches Produkt aus V und V)

Beispielgraph:

V={1,2,3,4} E={(1,2), (2,3), (4,1), (4,2), (3,1)}

Es gibt sowohl gerichtete als auch ungerichtete Graphen, wir sprechen hier über gerichtete Graphen, also Graphen, wo die Kanten einen Start- und einen Endknoten haben, bzw. wo die Kanten einen Pfeil haben. Hin- und Rückkanten wären also möglich.

Um schneller mit den Graphen arbeiten zu können (zum Beispiel ihn traversieren ¹⁾ ) benötigen wir bessere Repräsentationen seiner Kanten.

Bei der Adjanzenzliste speichern wir uns für jeden Knoten eine Liste seiner Nachbarn (gemeint ist hier die Knoten, die wir von ihm aus erreichen können). Wir benötigen also bei 4 Knoten im Graphen 4 solche Listen:

1 ⇒ 2
2 ⇒ 3
3 ⇒ 1
4 ⇒ 1,2

Die Adjanzenzliste repräsentiert also die Kantendarstellung von oben.

Die Adjazenzmatrix ist (im Allgemeinen) etwas größer als die Adjanzenzliste, wir wissen aber immer wie groß die Matrix ist, weil sie sich in der Größe nie verändern kann. So eine Adjanzenzmatrix speichert sich in der vertikalen die Startknoten und in der Horizontalen die Endknoten. Die Matrix für unser Beispiel von oben sieht also so aus: