16 Graphen

Graphen als Datenstruktur

Graphen als Datenstruktur sind uns in diesem Buch bereits mehrfach begegnet, etwa bei der Diskussion der verschiedenen Algorithmenmuster. Auch die bereits behandelten Bäume sind ein Spezialfall von Graphen. Tatsächlich handelt es sich bei Graphen um eine der wichtigsten Datenstrukturen in der Programmierung, die in vielen Anwendungsgebieten zum Einsatz kommen.

Ein Graph besteht grob gesprochen aus mit Kanten verbundenen Knoten. Unterschiede gibt es in der Art der Kanten sowie in der Realisierung der Kanten und Knoten in einer Datenstruktur, die sich auf die Effizienz der unterschiedlichen Graphenfunktionen auswirkt.

Wir werden zuerst verschiedene Arten von Graphen betrachten und dann mehrere Implementierungsvarianten ...

Get Algorithmen und Datenstrukturen, 5th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.