Der Algorithmus, den die Schüler*innen in diesem Modul kennengelernt haben, ist ein Algorithmus für die Suche nach dem kürzesten Pfad. In der Fachsprache heißt dieser Algorithmus Breadth-first Search-Algorithmus oder einfach BFS-Algorithmus. Im Deutschen wird er auch als „Breitensuche“ bezeichnet. Er wurde 1945 erfunden und ermöglicht es, einen Graphen zu durchlaufen, indem zunächst ein Ausgangsknoten, dann seine Folgeknoten, dann die nicht besuchten Folgeknoten der Folgeknoten usw. besucht werden. Mit dem Breitensuchalgorithmus können die Entfernungen aller Knoten von einem Ausgangsknoten in einem Graphen berechnet werden. Das Grundprinzip des BFS-Algorithmus besteht darin, den Startknoten an den Anfang zu setzen und dann alle seine Nachbarn, die noch nicht besucht wurden, zu einer Warteschlange hinzuzufügen. Bereits besuchte Knoten werden markiert, damit ein und derselbe Knoten nicht mehrmals besucht wird. Dieser Algorithmus funktioniert nur bei nicht gewichteten Graphen, d. h. Graphen, bei denen die Knoten durch Kanten verbunden sind, deren Kantenlängen alle gleich sind und die kein Kantengewicht haben. Das trifft auf die Graphen in diesem Modul zu: Zwei Knoten (hier: Konfigurationen) sind durch eine Kante verbunden, wenn man mit einer einzigen Kurbelbewegung von einer Konfiguration zur anderen gelangen kann. BFS dagegen funktioniert bei gerichteten und nicht gerichteten Graphen. Ein gerichteter Graph ist ein Graph, bei dem die Kanten zwischen zwei Knoten gerichtet sind, das heißt, sie verlaufen von einem Knoten zu einem anderen (Diestel, 2018) bzw. sie können nur in eine Richtung durchlaufen werden. Da das Spiel Involution© symmetrisch ist (wenn man von einer Konfiguration A zu einer Konfiguration B mit nur einer Kurbelbewegung gelangen kann, kann man mit der entgegengesetzten Bewegung von B nach A gelangen, was exakt die gleiche Bewegung ist), sind die Graphen in diesem Modul nicht gerichtet. Die Fakultät für Computerwissenschaften der Cornell University hat Videos mit einer Einführung in den BFS-Algorithmus veröffentlicht, mit einer Dauer von insgesamt 15 Minuten (Gries, n.d.).

In anderen Situationen als einem Spiel können die Graphen gewichtet sein. Der Graph des Straßennetzes, den wir in diesem Modul kennengelernt haben, ist ein gewichteter Graph: Die Entfernung zwischen zwei Kreuzungen variiert situationsabhängig und der Graph muss dem Rechnung tragen, indem er die Kanten gewichtet. Der kürzeste Pfad ist also nicht mehr unbedingt der Pfad, der die wenigsten Knoten durchläuft. BFS funktioniert daher nicht bei gewichteten Graphen. Der Algorithmus von Dijkstra ist ein bekannter Algorithmus, der den kürzesten Pfad für gewichtete (oder ungewichtete) gerichtete oder nicht gerichtete Graphen berechnet. Er ist nach seinem Erfinder Edsger Dijkstra benannt und wurde erstmals 1959 veröffentlicht (Dijkstra, 1959). Der Algorithmus von Dijkstra funktioniert wie folgt: Der Algorithmus beginnt bei einem Startknoten und berechnet die Entfernungen von diesem Knoten zu allen anderen Knoten im Graphen. Anschließend wählt er den Knoten mit der geringsten Entfernung zum Startknoten aus. Dieser Knoten wird zusammen mit dem Startknoten einer Warteschlange hinzugefügt, und anschließend werden alle Entfernungen neu bewertet: Wenn die Entfernung vom Startknoten zu einem Knoten kleiner ist, wenn ein neuer Knoten durchlaufen wird, wird sie durch die geringere Entfernung ersetzt. Der Algorithmus fährt auf diese Weise fort, bis er alle Knoten durchlaufen hat. So werden die Mindestentfernungen vom Startknoten zu allen anderen Knoten ermittelt. Die Fakultät für Computerwissenschaften der Cornell University hat auch eine Einführung in den Algorithmus von Dijkstra veröffentlicht (Gries, n.d.).

Der Mathematiker J. H. C. Whitehead sagte immer wieder, dass „die Kombinatorik das Armenhaus der Topologie ist“ (Cameron, 2011). Die Kombinatorik ist eine mathematische Disziplin, zu der auch die Graphentheorie gehört. Diese Einstellung zur Graphentheorie war zu Beginn des 20. Jahrhunderts unter vielen Mathematikern weit verbreitet, hat sich aber im Laufe der Zeit stark oder sogar vollständig gewandelt. Die Graphentheorie ist ein wichtiges Werkzeug zur Untersuchung von Verbindungen in komplexen Systemen. Sobald ein System schematisch in Form von Knoten und Kanten dargestellt werden kann, findet die Graphentheorie Anwendung. Diese Systeme können sehr unterschiedlich sein: Straßennetze, städtische Netze mit Computerdaten … Es gibt in der heutigen digitalen Welt unzählige Anwendungen. Hier einige sehr wichtige Beispiele (Flovik, 2020):

• Ansteckung mit dem Covid-19-Virus in der Gemeinschaft
• Ranking von Websites in Suchmaschinen (wie Google)
• Netzsicherheit
• GPS-Navigationssysteme
• usw.

Nehmen wir als Beispiel die GPS-Navigationssysteme (wie GoogleMaps, Waze usw.), die auch in diesem Modul vorkommen. GPS-Navigationssysteme gehören zu den Anwendungen der Graphentheorie, die direkt mit unserem Alltag zu tun haben: Sehr oft überlassen wir es diesen Systemen, uns auf dem kürzesten (oder schnellsten) Weg von A nach B zu bringen. Ein Straßennetz kann durch einen Graphen dargestellt werden, dessen Knoten Kreuzungen und Gebäude sind und dessen Kanten die Straßenabschnitte sind, die sie verbinden. Da bestimmte Straßen nur in eine Richtung führen, ist der Graph gerichtet (im Gegensatz zum Involution©-Graphen, der nicht gerichtet ist). Das Navigationssystem berechnet einen optimalen Pfad zwischen zwei Punkten im Netz, basierend auf den vom/von der Benutzer*in festgelegten Kriterien (es optimiert entweder die Länge der Strecke, die Fahrzeit oder bevorzugt Autobahnen usw.). Stellen wir uns in diesem Zusammenhang vor, dass das System versucht, die Länge der Strecke zu minimieren. Um das Problem zu modellieren, müssen wir dem gerichteten Graphen, der das Straßennetz modelliert, Informationen hinzufügen. Man weist also jedem Straßenabschnitt ein Gewicht zu, das genau der Länge dieses Abschnitts entspricht. Navigationssysteme verwenden daher gerichtete und gewichtete Graphen. Der Algorithmus zur Suche nach dem kürzesten Pfad, den die Navigationssysteme verwenden, basiert auf dem Algorithmus von Dijkstra (Teheux, 2019).

Interessant ist, dass die GPS-Navigationssysteme den Dijkstra-Algorithmus invers verwenden. Konkret bedeutet das: Wenn das Ziel des*r Benutzer*in*s darin besteht, von Knoten A zu Knoten B zu gelangen, dann wendet das Navigationssystem den Algorithmus von Dijkstra auf den ermittelten Graphen an, indem es die Kanten des Straßennetzgraphen mit Knoten B als Ausgangsknoten ausgibt. Das Ergebnis ist dann der kürzeste Weg von B nach A. Man muss diesen Weg aber nur umkehren, dann erhält man den gewünschten Weg. Die Idee hinter diesem inversen Verfahren ist eine Arbeitsersparnis bei den Berechnungen. Es kommt nicht selten vor, dass wir als Autofahrer*innen irgendwann den vom Navi empfohlenen Weg verlassen (wir fahren falsch, eine Straße ist für den Verkehr gesperrt, wir ändern unseren Plan in letzter Minute usw.). Wenn der Algorithmus die Suche nach dem kürzesten Weg in der richtigen Richtung durchgeführt hätte, müsste er von vorne beginnen (da wir uns an einem Ort befinden, der in den Berechnungen des Algorithmus nicht vorgesehen war) und alle vorher vorgenommenen Berechnungen wären hinfällig. Wenn man dagegen am Ende beginnt, hat der Algorithmus bereits den kürzesten Weg von einem beliebigen Punkt (innerhalb eines angemessenen Radius) zum Endpunkt berechnet. Dadurch ist der Algorithmus in der Lage, uns auch bei einer plötzlichen Änderung der Route schnell eine Alternative anzubieten (Teheux, 2019).

Obwohl die reine Graphentheorie eine abstrakte und mathematische Disziplin ist, wird deutlich, dass sie viele konkrete und interessante Anwendungen in der Informatik hat. Wie sagte der international bekannte Informatiker Leslie Lamport so schön: „Wenn Sie wirklich etwas richtig machen wollen, müssen Sie Ihren Algorithmus in den Begriffen der Mathematik schreiben“ (Han, 2022).

Referenzen
Cameron, Peter J. (2011). Aftermath. Preprint. https://arxiv.org/pdf/1111.4050.pdf
Diestel, Reinhard. (2018). Graph theory (5th Ed.). Graduate Texts in Mathematics, 173. Berlin : Springer.
Dijkstra, Edsger W. (1959). A note on two problems in connexion with graphs. Numer. Math., 1, 269 – 271. https://doi.org/10.1007/BF01386390 
Flovik, Vegard. (2020). What is Graph Theory, and why should you care. From graph theory to path optimization. Towards Data Science. https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2
Gries, David. (n.d.). Depth-first search and breadth-first search. https://www.cs.cornell.edu/courses/JavaAndDS/dfs/dfs01.html
Gries, David. (n.d.). The shortest-path algorithm. https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html
Han, Sheon. (2022). How to Write Software With Mathematical Perfection.Quantamagazine. https://www.quantamagazine.org/computing-expert-says-programmers-need-more-math-20220517
Teheux, Bruno. (2019). À la recherche des chemins les plus courts. Losange, N 46, 45-54.