Adjazenzlisten

Graphen können mithilfe von Adjazenzlisten, die die Nachbarschaftsverhältnisse der einzelnen Knoten enthalten, repräsentiert werden. Für jeden Knoten wird dazu eine Liste mit seinen adjazenten, also benachbarten Knoten erstellt. Unten das Beispiel vom gerichteten Graphen von gerade eben. Zur Erinnerung: Die Nachbarn eines Knotens sind dabei alle Knoten seiner ausgehenden Kanten.

Die einzelnen Listen können zum Beispiel in einem Array mit der Länge der Anzahl der Knoten gespeichert werden.

Erstelle für den folgenden Graphen seine Adjazenzlisten.

Erstelle aus den folgenden Adjazenzlisten einen Graphen.

• Erläutere, wie man einen gewichteten Graphen in einer Adjazenzliste speichern könnte.
• Beschreibe, wie die Adjanzenzliste aussehen würde, wenn der Graph ungerichtet wäre.

Überlege dir einen Graphen und einen Satz Adjazenzlisten für deinen Partner. Erkläre ihm dann anhand der Aufgaben 1 bis 3, was Adjazenzlisten sind und wie sie zu verstehen sind. Anschließend lässt du ihn zur Übung die Aufgaben hier lösen.