Tiefensuche auf Graphen
Im Vergleich zur Breitensuche, geht man bei der Tiefensuche von jedem besuchten Knoten direkt auf die benachbarten weiter. Im Allgemeinen wird dabei rekursiv die Suchfunktion für einen folgenden Knoten erneut aufgerufen. Die Schwierigkeit besteht, wie bei der Breitensuche, in der Vermeidung von mehrfachen Besuchen eines Knotens.
Ein denkbarer Algorithmus wäre:
- Bestimme den Knoten, an dem die Suche beginnen soll und setze diesen als aktuellen Knoten.
- Speichere die ID des Knoten in einem Array mit schon besuchten Knoten.
- Ist der aktuelle Knoten der gesuchte Knoten?
- Rufe für jeden Nachbarn rekursiv die Tiefensuche auf, aber nur wenn der gesuchte Knoten noch nicht gefunden wurde, und der Nachbarknoten nicht schon besucht wurde.
- Überlegen Sie sich, wie die Tiefensuche ein Objekt findet, indem Sie den vorhandenen Graphen durchlaufen.
- Ist der Algorithmus besser oder schlechter als die Breitensuche?
- Was sind Vor- und was sind Nachteile?