Repräsentation von Graphen

Einstieg: Zwei Beispiele

Darstellung als Adjazenzmatrix oder als Adjazenzliste

Übungen

(A4)

Stelle folgende als Adjazenzmatrix oder Adjazenzliste gegebenen Graphen dar.

Lösung

(A5)

Betrachte die Dateien graph1.csv und graph2.csv im Unterordner beispielgraphen/05_repraesentation des Graphen-Testers in einem Texteditor. Untersuche, wie die Graphen hier gespeichert sind.

Lösung

Beide Dateien beginnen mit einigen Basisinformationen über den Graphen, dann kommt der eigentliche Graph. graph1.csv enthält eine Adjazenzliste, graph2.csv eine Adjazenzmatrix. In beiden Formaten ist für jeden Knoten eine Zeile gespeichert. Neben den Kanten des Knoten ist noch die Position des Knotens abgespeichert. Die erste Zahl ist die x-Koordinate, die zweite Zahl die y-Koordinate. Das ist notwendig, um den Graphen zeichnen zu können, für die Algorithmen nicht. graph1.csv ist ein ungewichteter Graph. Daher sind nur die Nummern der Knoten angegeben, wohin die Kanten führen. Bei graph2.csv handelt es sich um einen gewichteten Graph. Daher sind die Matrixeinträge die Gewichte der Kanten.