Graph Tiefensuche
-
Hey alle zusammen,
ich bin gerade dabei mich ein wenig durch die theoretische Programmierung zu fressen und bin nun auf die Graphen gestoßen. Dabei bin ich zuletzt bei dir Breiten- und Tiefensuche hängen geblieben. Den Nutzen von Ersteren hab ich schon erkannt (den Kürzesten Pfad von einem Startknoten zu jedem anderen Knoten ermitteln). Allerdings habe ich nicht durchblickt, was mir die Tiefensuche eigentlich bringt. Kann sie mir auch den kürzesten Abstand von einem bestimmten Knoten liefern oder hat sie andere Funktionen?Ich hoffe ihr könnt mir weiterhelfen
Grüße
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
-
Kann sie mir auch den kürzesten Abstand von einem bestimmten Knoten liefern oder hat sie andere Funktionen?
Naja, wie der Name schon sagt, es ist eine Art Knoten im Graphen zu suchen. Und im Gegensatz zur Breitensuche klapperst du nicht erst alle Nachbarknoten deines Startknotes ab, sondern gehst erstmal sofort immer "tiefer", bis es nicht mehr weiter geht, bzw. du irgendwo angelangt bist, wo du schonmal warst.
Einen kürzesten Weg findest du damit erstmal nicht. Dabei hilft dir die Breitensuche eher weiter, schau dir z.B. mal dies hier an: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus