Repräsentation mit Nachbarschaftslisten

Knoten und ihre Nachbarn

Wir betrachten weiterhin den folgenden Graphen:

Zur Repräsentation des Graphen kann man jedem Knoten eine Liste (eine sog. Adjazenzliste) mit den zugehörigen Nachbarknoten zuordnen:

A: B
B: B, C, D
C: A, B
D:

Aufgabe 1

(a) Wie liest man diese Darstellung?

(b) Ergänze die Nachbarschaftslisten so, dass sie den folgenden erweiterten Graphen beschreibt.

(c) Wie könnte man entsprechend einen gewichteten Graphen beschreiben?.

Aufgabe 2

Wie könnte man eine Ansammlung von Nachbarschaftslisten (in Python) implementieren? Mache hierzu einen Vorschlag.