Tiefensuche implementiert mit Rekursion: Unterschied zwischen den Versionen

Version vom 8. Februar 2014, 13:04 Uhr

In Bearbeitung

Ansporn

Einen Graphen durchlaufen. Hierbei sollen alle Knoten mindestens ein Mal besucht worden sein, aber es müssen nicht alle Kanten einmal besucht werden.

Zielsetzung

Implementierung

void TiefenSuche(String BezNeu) // Anfang der Methode mit BezNeu als Eingangsparameter

   {
       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

   }