Implementierung einer Nachbarschaftstabelle
Implementierung mit Listen
Wir betrachten weiterhin den folgenden Graphen:
Die Nachbarschaftstabelle zu diesem Graphen lässt sich in Python mit Hilfevon Listen nachbilden.
knotenliste = ['A', 'B', 'C', 'D'] adjazenzmatrix = [[0, 1, 0, 0], [0, 1, 1, 1], [1, 1, 0, 0], [0, 0, 0, 0]]
Aufgabe 1
(a) (einfach)
Entwickle eine Funktion existiertKnoten(nameKnoten)
, die
überprüft, ob ein vorgegebener Knoten im Graph vorkommt.
Teste das Verhalten der Funktion, z.B. so:
>>> knotenliste = ['A', 'B', 'C', 'D'] >>> adjazenzmatrix = [[0, 1, 0, 0], [0, 1, 1, 1], [1, 1, 0, 0], [0, 0, 0, 0]] >>> existiertKnoten('D') True >>> existiertKnoten('G') False
(b) (etwas schwieriger)
Entwickle eine Funktion existiertKante(nameStartKnoten, nameZielKnoten)
, die überprüft,
ob es eine Kante zwischen den übergebenen Knoten gibt.
Teste das Verhalten der Funktion, z.B. so:
>>> knotenliste = ['A', 'B', 'C', 'D'] >>> adjazenzmatrix = [[0, 1, 0, 0], [0, 1, 1, 1], [1, 1, 0, 0], [0, 0, 0, 0]] >>> existiertKante('A', 'D') False >>> existiertKante('B', 'D') True >>> existiertKante('X', 'Y') False
Tipp: Mit knotenliste.index('A')
kann man den Index des übergebenen Bezeichners in
der Knotenliste bestimmen.
(c) (noch etwas schwieriger)
Entwickle eine Funktion getAlleNachbarn(nameKnoten)
, die sämtliche Nachbarn eines vorgegebenen
Knotens ermittelt und zurückgibt.
>>> knotenliste = ['A', 'B', 'C', 'D'] >>> adjazenzmatrix = [[0, 1, 0, 0], [0, 1, 1, 1], [1, 1, 0, 0], [0, 0, 0, 0]] >>> getAlleNachbarn('B') ['B', 'C', 'D']
Objektorientierte Modellierung
Für die weitere Verarbeitung von Graphen ist es günstig, Graphen als Objekte
einer Klasse Graph
zu realisieren.
Aufgabe 2
(a) Überlege dir, welche Operationen ein Graph
-Objekt ausführen können soll.
Einige Operationen werden bereits in Aufgabe 1 thematisiert.
Erstelle ein Klassendiagramm zur Dokumentation der Klasse.
(b) Implementiere die Klasse Graph
. Teste die Implementierung mit einem
geeigneten Python-Dialog oder einem einfachen Testprogramm.