Tiefensuche implementiert mit Rekursion: Unterschied zwischen den Versionen

Aktuelle Version vom 17. März 2014, 17:15 Uhr

Die Tiefensuche ist neben der Breitensuche ein elementarer Algorithmus zum Graphendurchlauf.

Zielsetzung

Die Aufgabenstellung ist einen Graphen zu durchlaufen. Hierbei sollen alle Knoten mindestens ein Mal besucht worden sein, aber es müssen nicht alle Kanten einmal besucht werden.

Zum Namen

Tiefensuche kommt daher, weil zuerst in der Tiefe gesucht wird. Ist man dann in einer Sackgasse angekommen, geht man wieder zurück, bis es wieder eine Abzweigung gibt.

Algorithmus

1. Besuche einen Nachbarknoten. Falls mehrere Wege möglich sind wähle einen beliebigen
2. Besuchte Knoten werden markiert und in 1. nicht mehr berücksichtigt.
3. Wenn es keine unbesuchten Knoten gibt, gehe einen Schritt zurück.

Implementierung

/**
*Die Methode "TiefenSuche" wird vom User aufgerufen und hat folgende Aufgaben:
*1. Prüfen ob der angegebene Knoten Existiert und heraussuchen des Indexes
*2. Alle Knoten unbesucht machen (Für den Fall das die Methode mehrmals aufgerufen wird
*3. Aufrufen der "Hauptmethode" 
*/

void TiefenSuche(String BezNeu)

   {
       int startNummer; 
       startNummer =this.KnotenNummer(BezNeu);  // Der Variable startNummer wird der Index des Knotens zugewiesen
       if(startNummer!=-1) // Es wird geprüft ob dieser Knoten überhaupt existiert
       {
           for(int i=0;i<aktuelleAnzahlKnoten;i++) // Bei allen Knoten…
           {
               knoten[i].MarikierungLoeschen();    //...wird die Varialbe auf IstNichtBesucht gesetzt
                                                   // Es ist auch anders möglich z.B. mit einem Array
           }
           System.out.println(" Starte Tiefensuche mit "+ BezNeu); //Info für den User
           this.Besuchen (startNummer); //Start der Eigetlichen Tiefensuche
           System.out.println("Fertig mit TiefenSuche"); //Info für den User
       }
       else
       {
           System.out.println("Knoten existiert nicht"); //Info für den User
       }
   }

void Besuchen (int knotenNummer) //Hauptmethode

   {
       knoten[knotenNummer].MarikierungAendern();	//Dieser Knoten wird als Besucht angesehen
       System.out.print("besuch " + knoten[knotenNummer].BeschreibungGeben() + "; "); //Info für den User
       for(int  i =0;i<aktuelleAnzahlKnoten;i++)  //Die Adjazenzmatrix von links nach rechts durchlaufen
       {
           if(matrix[knotenNummer][i]>0&&knoten[i].MarkierungGeben()==false) //Wenn bei i ein 
//Knoten existiert und er noch nicht besucht wurde dann… 
           {            
               Besuchen(i); 	//rekursiver Methodenaufruf
               System.out.print("zurueck nach " + knoten[knotenNummer].BeschreibungGeben() + "; ");//Info für den User
           } 
       }
       System.out.println("fertig mit " + knoten[knotenNummer].BeschreibungGeben() + "; ");  //Info für den User
   }

Test der Methode

Das ist die Adjazenzmatrix meiner Test Klasse. (Siehe Buch)

     |  FD   |  WUE  |  N    |  HO   |  R    |  M    |  RO   |  LI   |  UL   |  S    |  A    | 
FD   | 0     | 3     |       |       |       |       |       |       |       |       |       | 
WUE  | 3     | 0     |       | 7     |       |       |       |       | 8     |       |       | 
N    |       |       | 0     | 9     |       | 1     |       |       |       |       |       | 
HO   |       | 7     | 6     | 0     | 4     |       |       |       |       |       |       | 
R    |       |       |       | 5     | 0     | 9     |       |       |       |       |       | 
M    |       |       | 7     |       | 4     | 0     | 5     |       |       |       | 3     | 
RO   |       |       |       |       |       | 6     | 0     |       |       |       |       | 
LI   |       |       |       |       |       |       |       | 0     | 4     |       |       | 
UL   |       | 2     |       |       |       |       |       | 8     | 0     | 8     | 5     | 
S    |       |       |       |       |       |       |       |       | 13    | 0     |       | 
A    |       |       |       |       |       | 6     |       |       | 3     |       | 0     |  

Dies ist die Ausgabe wenn man die Methode Tiefensuche mit dem Parameter R aufruft.

Starte Tiefensuche mit R
besuch R; besuch HO; besuch WUE; besuch FD; fertig mit FD; 
zurueck nach WUE; besuch UL; besuch LI; fertig mit LI; 
zurueck nach UL; besuch S; fertig mit S; 
zurueck nach UL; besuch A; besuch M; besuch N; fertig mit N; 
zurueck nach M; besuch RO; fertig mit RO; 
zurueck nach M; fertig mit M; 
zurueck nach A; fertig mit A; 
zurueck nach UL; fertig mit UL; 
zurueck nach WUE; fertig mit WUE; 
zurueck nach HO; fertig mit HO; 
zurueck nach R; fertig mit R; 
Fertig mit TiefenSuche

Vorteil und Nachteil

Vorteil:

• Alle Knoten werden sicher Besucht. D.h. die Aufgabe wurde sicher erfüllt.

Nachteil:

• Nicht "intelligent" d.h. nicht der schnellste oder kürtzeste Weg wird gewählt, sondern ein (für einen Aussenstehenden) willkürlicher.