Kantenlisten

Kantenlisten sind eine einfache Methode zur Darstellung von Graphen, bei der alle Kanten als Tupel gespeichert werden. In einem ungerichteten Graphen ist eine Kante typischerweise als (u, v) definiert, in einem gerichteten Graphen als (u, v). Bei gewichteten Graphen ergänzt man das Tupel um das Gewicht, z. B. (u, v, w). Je nach Restiktionssätzen können auch Mehrfachkanten oder Schleifen enthalten sein.

Die Speicherung erfolgt meist als Liste oder Sequenz von Kanten. Diese Darstellung eignet sich gut für Graphen mit relativ wenigen Kanten gegenüber der Anzahl möglicher Verbindungen und wenn primär über die Kanten iteriert werden soll. Der Zugriff auf die Nachbarn eines bestimmten Knotens ist ineffizient im Vergleich zu Adjazenzlisten; eine Kante zwischen zwei Knoten zu finden, kann linear in der Liste dauern. Sortiert man die Kantenliste, lassen sich Suchvorgänge per Binärsuche beschleunigen, doch generelle Änderungen der Struktur (Hinzufügen/Entfernen von Kanten) können teurer sein.

Im Vergleich zu Adjazenzlisten speichert die Kantenliste jede Kante nur einmal, was bei dünn besetzten Graphen speicherfreundlich sein kann. Gegenüber Adjazenzmatrizen benötigt sie deutlich weniger Speicherplatz bei großen Graphen, ist aber weniger geeignet für dichte Graphen, da dort die Repräsentation ineffizient werden kann.

Anwendungen finden sich in Algorithmen, die direkt mit der Menge der Kanten arbeiten, wie dem Kruskal-Minimum-Spanning-Tree-Algorithmus, oder beim Einlesen von Graphen aus tex-basierten Formaten, in denen Kanten als Zeilen dargestellt werden. Kantenlisten sind eine grundlegende Darstellungsform in vielen Lehr- und Praxisfällen, wenn Einfachheit und direkte Verarbeitung der Kanten im Vordergrund stehen.