Tiefensuche implementiert mit Rekursion: Unterschied zwischen den Versionen

Version vom 11. Februar 2014, 15:28 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

/**

• Diese Methode wird vom User aufgerufen und hat folgende Aufgaben:
• 1. Prüfen ob der angegebene Knoten Existiert und herraus suchen 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
   }