Graphsuche
Definition
Graphsuche findet Knoten oder Verbindungen, indem ein Algorithmus Beziehungen in einem Graphen untersucht.
Ein Graph besteht aus Knoten und Kanten. Bei der Suche bestimmt eine Strategie, welche erreichbaren Knoten als Nächstes untersucht werden: Die Breitensuche geht nach Ebenen vor, die Tiefensuche verfolgt zunächst einen Zweig.
Einfach erklärt
Stell dir ein Wegenetz vor. Du kannst erst alle direkten Nachbarorte prüfen oder einem Weg weiter folgen. Der Vergleich erklärt die Reihenfolge, nicht die Wahl des besten Verkehrswegs.
Warum das im Alltag wichtig ist
Für die Auswahl eines Suchverfahrens sind die Fragestellung und die Struktur der Beziehungen entscheidend. Die Reihenfolge der Erkundung ist Teil des Verfahrens.
Beispiel aus dem Mittelstand
Mögliches Beispiel: Ein Betrieb untersucht, welche Anlagen über mehrere Lieferbeziehungen mit einem Bauteil verbunden sind.
Grenzen und Fallstricke
- Ein gefundener Weg ist nicht automatisch der kürzeste oder günstigste. Suchziel, Kanteneigenschaften und Umgang mit bereits besuchten Knoten müssen feststehen.
Entstehung & Geschichte
NIST dokumentiert Breitensuche und Tiefensuche als unterschiedliche Suchstrategien. Die herangezogenen Lexikoneinträge wurden 2019 beziehungsweise 2021 inhaltlich aktualisiert; daraus folgt kein Erfindungsjahr der Graphsuche.
Anwendung im Mittelstand
- Denkbar ist die Untersuchung von Abhängigkeiten in einer Lieferkette. Vorab ist festzulegen, welche Beziehung eine Kante darstellt und wann die Suche endet.
Häufige Fragen
Sind Breitensuche und Tiefensuche dasselbe?
Nein. Sie unterscheiden sich in der Reihenfolge der untersuchten Knoten.
Liefert jede Graphsuche den besten Weg?
Nein. Das hängt von Verfahren, Suchziel und Bewertung der Kanten ab.
Quellen
- breadth-first search · Paul E. Black (2019): breadth-first search
- depth-first search · Paul E. Black (2021): depth-first search
Redaktionell geprüft am: