Repräsentation mit Nachbarschaftslisten

Knoten und ihre Nachbarn

Wir betrachten weiterhin den folgenden Graphen:

Graph 1

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.

Graph 2

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

Graph 2

Aufgabe 2

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

X

Fehler melden

X

Suche