Kantenliste

Kantenliste (edge list) ist eine Darstellungsform eines endlichen Graphen, bei der der Graph durch eine Menge von Kanten beschrieben wird. Jede Kante wird dabei als Paar von Knoten angegeben; bei gewichteten Graphen enthält die Kante zusätzlich ein Gewicht. Bei gerichteten Graphen werden Kanten als geordnete Paare (U,V) notiert; für ungerichtete Graphen genügt ein ungerichtetes Paar, wobei die Richtung egal ist.

Eine typische Textdarstellung besteht aus einer Liste von Zeilen, wobei jede Zeile eine Kante repräsentiert, z. B. 1 2 oder 1 2 5 für eine Gewichtung. Das Format ist einfach, flexibel und wird häufig als Eingabeformat für Graph-Algorithmen wie Kruskal oder Dijkstra verwendet. Es kann auch Dateien mit einer Kantenliste geben, in der mehrere Kanten desselben Paares auftreten, um Mehrfachkanten zu kennzeichnen.

Speicher- und Laufzeitkomplexität: Eine Kantenliste benötigt O(m) Speicher für m Kanten; im Worst-Case bei einem dichten Graphen kann dies O(n^2) werden. Operationen wie das Prüfen, ob eine bestimmte Kante existiert, erfordern typischerweise O(m) Zeit, es sei denn, es bestehen zusätzliche Indizes. Die Kantenliste eignet sich gut für das Iterieren der Kanten, nicht so gut für Nachbarschaftsabfragen.

Vergleich: Im Gegensatz zur Nachbarschaftsliste fasst die Kantenliste Kanten unabhängig von Knoten zusammen; die Adjazenzmatrix ermöglicht schnelle Nachbarschaftsabfragen, benötigt aber O(n^2) Speicher. Kantenlisten sind einfach zu erzeugen, zu speichern und zu übertragen, besonders für spärliche Graphen.

Beispiel: Ein ungerichteter Graph mit vier Knoten {1,2,3,4} und Kanten {(1,2), (1,3), (2,4), (3,4)} wird als Zeilenliste dargestellt: 1 2; 1 3; 2 4; 3 4. Ein gewichteter Graph könnte zusätzlich die Gewichte 5, 3, 7, 4 enthalten: 1 2 5; 1 3 3; 2 4 7; 3 4 4.