17.04.2019
Diese Seite handelt von Algorithmen für die Suche in Graphen. Oben sehen sie die Technik ‘Breitensuche’ (engl. ‘breadth first search’ - BFS) bei der Arbeit. Der Algorithmus sucht einen Pfad durch den Graphen vom vollen grünen Knoten auf der linken Seite zum roten Knoten rechts. Die Knoten werden dunkelgrün eingefärbt when sie von der Suchfunktion gefunden werden, genauso wie die Kanten über die sie gefunden wurden. Beachten sie, dass nicht alle Kanten genutzt werden, da die meisten Knoten über mehrere Pfade gefunden werden können. Falls ein Pfad vom Startknoten zum Endknoten existiert, wird BFS ihn finden. Mit dieser Technik arbeitet die Suche sozusagen ‘blind’, sie weiss also nicht wie nah oder fern sie vom Zielknoten ist. Andere Techniken benutzen eine sogenannte Heuristik um das Ziel zu finden, was wir später auf anderen Seiten behandeln werden.
Die hier gezeigten Graphen sind ungerichtet, planar und haben keine doppelten Kanten. Ungerichtet heißt, dass Kanten von beiden Seiten überschritten werden können, und planar bedeutet, dass man den Graphen auf einer Ebene darstellen kann, ohne das sich die Kanten überschneiden. Keine doppelten Kanten bedeutet, dass zwei Knoten höchstens eine Kante zwischen sich haben.
Hier sehen sie die Vergrößerung eines kleineren Graphen, damit wir die Vorgänge in mehr Detail zeigen können. Unter dem Graphen sieht man die Warteschlange, gefüllt mit Knoten die als nächstes durchsucht werden sollen. Die Zahlen in den Knoten dienen der Identifikation. In der Breitensuche wird jeder neue Knoten der gefunden wird ans Ende der Warteschlange eingefügt (rechtes Ende). Die Suche bewegt sich forwärts indem neue Knoten vom Anfang der Warteschlange entnommen werden (linkes Ende). Falls die BFS Suche mit einer leeren Warteschlange abbricht, sind die Start- und Endknoten nicht in der selben Komponente, und die Suche wird alle Knoten in der eigenen verbundenen Komponente erforscht haben. Mehr über Komponenten weiter unten auf dieser Seite.
Die nächste Art einen Graphen zu durchsuchen, wie oben gezeigt, ist die ‘Tiefensuche’ (engl. ‘depth first search’ - DFS). Wenn diese Suche in eine Sackgasse gerät, macht sie weiter oben im genommenen Pfad weiter, um neue Knoten zu finden. Die Tiefensuche findet alle Knoten in der Komponente, genau wie die Breitensuche, aber findet sie in anderer Reihenfolge.
Im Gegensatz zu einer Warteschlange (‘first-in first-out’ Prinzip) benutzt die Tiefensuche einen Stapel (‘last-in first-out’ Prinzip) um die neuen Knoten zu speichern. Der Stapel wird hier unter dem Graphen dargestellt, und wächst nach rechts.
Eine Anwendung von Graphsuchen ist es, die verschiedenen verbundenen Komponenten eines Graphen zu identifizieren. Wenn es also keinen Pfad zwischen zwei Knoten gibt, befinden sie sich per Definition in verschiedenen Komponenten, es gibt also eine Lücke. Um die Komponenten zu identifizieren kann man entweder Breitensuche oder Tiefensuche verwenden, hier verwenden wir letzteres. Wenn es keine weiteren Knoten für die Suche zu finden gibt, ist die vollständige Komponente gefunden. Dann wählen wir einfach einen neuen, unerforschten Knoten des Graphen, und fangen von vorne an um die nächste Komponente zu identifizieren, bis alle Knoten abgearbeitet sind. Dieser Algorithmus ist oben zu sehen, wobei unterschiedliche Farben für unterschiedliche Komponenten verwendet werden.
Die bisher betrachteten Graphen waren ungerichtet, die Kanten hatten also keine Richtung und konnten von beiden Seiten durchquert werden. Viele praktische Graphen sind aber gerichtet, so wie das Beispiel zu diesem Abschnitt. Die Kanten können also nur in Richtung der gezeigten Pfeile durchquert werden. Hier sehen wir wieder eine Breitensuche vom grün gefüllten Knoten zum roten. Beachten sie, dass die Suche oft stecken bleibt, und keine neuen Knoten durchsucht werden können. Dies rührt daher das es in gerichteten Graphen weniger Pfade zu finden gibt.
Im allgemeinen enthalten gerichtete Graphen Zyklen. Das bedeutet, es gibt geschlossene Schleifen durch die gerichteten Kanten zurück zum Startknoten. Die Animation oben zeigt die im Graphen gefundenen Schleifen. Es ist wünschenswert einen Graphen frei von Schleifen zu haben, und dies ist das Thema der letzten Abschnitte unten.
Nachdem wir einen Graphen mit Zyklen gezeigt haben, ist hier ein Beispiel eines gerichteten Graphen ohne Zyklen (engl. ‘directed, acyclic graph’ - DAG). Er wurde generiert indem wir sichergestellt haben, dass alle Kanten rechtswärts gerichtet sind, was die Bildung von Zyklen verhindert. Jeder DAG hat mindestens eine Quelle, also einen Knoten mit nur ausgehenden Kanten. Die Quellen sind oben grün gekennzeichnet. Eine Senke hat nur einfallende Kanten und diese sind in rot gekennzeichnet. DAGs haben andere gute Eigenschaften, zum Beispiel haben sie stets eine topologische Sortierung. Die ist das Thema des letzten Abschnitts.
Eine topologische Sortierung ist eine lineare Darstellung eines DAG, bei dem alle gerichteten Kanten in die selbe Richtung weisen. Mit anderen Worten gibt es keine rückwärts gerichteten Kanten und so auch keine Zyklen. Eine topologische Sortierung zu finden ist ziemlich einfach: man führt eine Tiefensuche aus, und jedes mal wenn alle nachfolgenden Knoten eines Knotens abgearbeitet worden sind, erhält dieser Knoten die nächste Zahl, rückwärts zählend und beginnend beim letzten Knoten. Dies ist die Bedeutung der Zahlen in den Knoten. Die Tiefensuche wird einmal bei jeder Quelle angefangen, bis alle Knoten bearbeitet worden sind. Man beachte, dass es mehr als eine topologische Ordnung eines Graphen geben kann.
Ich hoffe ihnen hat diese animierte Erklärung der Graphensuche gefallen, warten sie auf die nächste Folge dazu und auf mehr Inhalte auf unserer Homepage.