Die Boost C++ Bibliotheken

Kapitel 31. Boost.Graph

Inhaltsverzeichnis

Die Bibliothek Boost.Graph bietet Werkzeuge an, um mit Graphen zu arbeiten. Graphen sind zweidimensionale Punktwolken mit beliebig vielen Verbindungslinien zwischen Punkten. Ein U-Bahn-Plan ist ein Beispiel für einen Graph: U-Bahnhöfe sind Punkte, die über U-Bahnlinien verbunden sind.

Die Graphentheorie ist der Teilbereich der Mathematik, der sich mit Graphen beschäftigt. Dort wird zum Beispiel der Frage nachgegangen, wie man den kürzesten Weg zwischen zwei Punkten in einem Graphen findet. Dieses Problem muss jedes Navigationssystem lösen, wenn es einen Autofahrer auf dem kürzesten Weg zu seinem Ziel lotsen will. Graphen haben daher eine hohe praktische Relevanz. Viele Probleme lassen sich auf Graphen zurückführen und können mit ihnen gelöst werden.

Boost.Graph bietet Container an, um Graphen zu definieren. Viel wichtiger aber sind die von Boost.Graph zur Verfügung gestellten Algorithmen, um zum Beispiel kürzeste Wege zu finden. Wie Sie Container und Algorithmen von Boost.Graph verwenden, erfahren Sie im Folgenden.