inf-schule | Repräsentation von Graphen » Implementierung von Nachbarschaftslisten

Implementierung von Nachbarschaftslisten

Implementierung mit Listen

Wir betrachten weiterhin den folgenden Graphen:

Die Nachbarschaftslisten zu diesem Graphen lassen sich in Python direkt nachbilden.

testGraph = \
[
    ['A', ['B']],
    ['B', ['B', 'C', 'D']],
    ['C', ['A', 'B']],
    ['D', []]
]

Aufgabe 1

(a) (einfach) Entwickle eine Funktion getAlleNachbarn(nameKnoten), die sämtliche Nachbarn eines vorgegebenen Knotens ermittelt und zurückgibt. Teste das Verhalten der Funktion, z.B. so:

>>> testGraph = \
          [
             ['A', ['B']],
             ['B', ['B', 'C', 'D']],
             ['C', ['A', 'B']],
             ['D', []]
          ]
>>> getAlleNachbarn('B')
['B', 'C', 'D']

(b) (schwieriger) Entwickle eine Funktion existiertKnoten(nameKnoten), die überprüft, ob ein vorgegebener Knoten im Graph vorkommt. Teste das Verhalten der Funktion, z.B. so:

>>> testGraph = \
          [
             ['A', ['B']],
             ['B', ['B', 'C', 'D']],
             ['C', ['A', 'B']],
             ['D', []]
          ]
>>> existiertKnoten('D')
True
>>> existiertKnoten('G')
False

(c) (noch 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:

>>> testGraph = \
          [
             ['A', ['B']],
             ['B', ['B', 'C', 'D']],
             ['C', ['A', 'B']],
             ['D', []]
          ]
>>> existiertKante('A', 'D')
False
>>> existiertKante('B', 'D')
True
>>> existiertKante('X', 'Y')
False

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.