/*************************  Graph_Tiefensuche.java ****************************/

/**    Tiefensuche auf einem Graphen                                         */

public class Graph_Tiefensuche {                // Tiefensuche auf Graphen

  static int id=0;                              // Variable fuer lfd. Nummer
  static boolean[]besucht;                      // zum Notieren, wer besucht ist
  static int[]ergebnis;
 
  private static void visit (Graph g, int k ) { // Tiefensuche beginnend bei k
    int x;                                      // Knotenname
    ergebnis[id++]=k;                           // notiere Knoten im Ergebnis 
    besucht[k] = true;                          // markiere als besucht

    g.reset(k);                                 // setze Nachbarn von k zurueck
    while (g.moreNeighbors(k)) {                // solange es noch Nachbarn gibt
      x =  g.nextNeighbor(k);                   // besorge naechsten Nachbarn
      if (!besucht[x]) visit(g,x);              // starte ggf. neue Rekursion
    }
  }

  public static int[]tiefensuche (Graph g) {    // oeffentliche Methode 

    int k;                                      // aktueller Knoten
    besucht = new boolean[g.number()];          // lege array besucht an 
    ergebnis= new int[g.number()];              // lege array ergebnis an 

    for (k=0; k<g.number(); k++)                // notiere jeden Knoten
      besucht[k]=false;                         // als nicht besucht

    for (k=0; k<g.number(); k++)                // fuer jeden nicht besuchten
      if (!besucht[k]) visit(g,k);              // Knoten starte Rekursion 

   return ergebnis;                             // liefere Ergebnis
  }
}