Breiten- und Tiefensuche
Die Breiten- und Tiefensuche ist eine Art der Traversierung im Graphen. Dies bedeutet, dass bei einem gegebenen Startknoten ein weiterer Zielknoten gesucht werden kann. Wie dieser Zielknoten gesucht wird, wird durch die Suchstrategie beschrieben. Die Breiten- und Tiefensuche stellen zwei Arten dieser Suchstrategien dar.
l. Breitensuche, r. Tiefensuche
Man unterschiedet zwischen zwei Arten der Breiten- bzw. Tiefensuche. Wird ein Zielknoten gesucht, bricht die Suche ab, sobald dieser gefunden wurde. Ist dieser Knoten im Graph nicht vorhanden, so wird der gesamte Graph zunächst durchsucht und die Suche endet erst, wenn alle Knoten durchlaufen wurden. Möchte man alle vorhandenen Knoten und ihre Beziehungen untereinander darstellen, muss ebenfalls der gesamte Graph durchlaufen werden. Ein Zielknoten wird hier nicht definiert.
Die Breitensuche durchsucht den Graphen, indem sie zuerst alle Nachbarknoten des Startknotens durchsucht. Im nächsten Schritt werden die Nachbarn der Nachbarn durchsucht. Die Pfadlänge wird mit jeder Iteration erhöht und jeder Knoten, der bereits besucht wurde, wird markiert. Wird ein Knoten gefunden, der bereits bereits durch einen kürzeren Pfad im Graph gefunden wurde und entsprechend markiert, wird dieser Knoten mehr neu besucht.
Als Beispiel sei hier ein Freundschaftsnetzwerk aufgeführt. Möchte man wissen, über wie viel Ecken eine Person mit einer anderen befreundet ist, ist es ausreichend die kürzeste Verbindung anzuzeigen. Weitere Verbindungen zu dieser Person müssen nicht mehr gespeichert werden. Nicht zu verwechseln ist dies mit einer Navigation und alternativen Routen. Hier wird für jede alternative Route eine neue Suche mit unterschiedlichen Parametern gestartet. Beispiele für diese Parameter können sein: kürzeste Strecke, schnellste Strecke, keine Autobahnen, usw. Auch hier wird pro Suche jeder Knoten nur einmal durchlaufen und markiert.
Anders als bei der Breitensuche verfolgt die Tiefensuche eine Pfad solange, bis sie an einem Knoten kommt, der keine ausgehenden Kanten hat (dieser Knoten ist dementsprechend eine Sackgasse des Suchpfades). Der Pfad wird nun rückwärts verfolgt, bis ein Knoten kommt, der noch weitere ausgehende Kanten besitzt. Hier wird die Suche fortgesetzt.
Quellen:
- Edlich, Friedland, Hampe, Brauer: "NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen", Hanser-Verlag, 2010, ISBN 978-3-446-42355-8
- Prof. Dr. Peter Sanders, Dipl.-Inform. Johannes Singler: "Berechnung kürzester Wege", http://algo2.iti.kit.edu/singler/algorithmus-der-woche/Kuerzeste%20Wege.pdf, Stand Mai 2011
- Prof. Dr. Bernhard Schiefer: "Algorithmische Graphentheorie", http://www.informatik.fh-kl.de/~schiefer/lectures/download/GT_7.pdf, Stand Mai 2011
- Thomas Hofmeister: "Randomisierte Algorithmen", http://www14.informatik.tu-muenchen.de/lehre/2006WS/ra/Hofmeister.pdf, 2006, Stand Mai 2011
- Alexander Esser: "Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen",1. Auflage, GRIN Verlag, 2009, ISBN 978-3-640-39550-7
Weiterführende Literatur:
- Prof. Dr. rer. nat. Peter Tittman: "Graphentheorie", Fachbuchverlag Leipzig im Carl Hanser Verlag, 2003, ISBN 3-446-22343-6
- Prof. Dr. Volker Turas: "Algorithmische Graphentheorie", 3. Auflage, Oldenburg Wissenschaftsverlag, 2009, ISBN 978-3-486-59057-9
- Bucher Gruppe: "Graphentheorie: Wege, Pfade, Zyklen und Kreise in Graphen, Durchlaufbarkeit Von Graphen, Vier-Farben-Satz, Zusammenhang Von Graphen", General Books LLC, 2010, ISBN 978-1-159-11215-8
- Steffi Meier: "Graphentheoretische Modelle zur Optimierung und Simulation", 1. Auflage, GRIN Verlag, 2006, ISBN 978-3-640-32530-6
Kategorie: Neue DB-Entwicklungen,NoSQL, Graphen-DB, B, T