Sitzung 4

Algorithmus, um einen Zyklus zu entdecken

function dfs (v)
  if v als besucht markiert
  then 
    if v als auf_pfad_besucht markiert
      then return true; // Zyklus gefunden
      else return false; // kein Zyklus
    endif
  else
    verarbeite v;
    markiere v als besucht; 
    markiere v als auf_pfad_besucht;
    zyklus = false; 
    for each Sohn vi von v do
      zyklus = zyklus OR dfs(vi);
    endfor
    lösche Markierung auf_pfad_besucht von v;
    return zyklus;
  endif
endfunction

Programm in Java

class Graph{
  int anzahl;
  boolean[][] adjazenz;
  boolean[] besucht;
  boolean[] auf_pfad_besucht;
  
  public Graph(int i){
    anzahl = i;
    adjazenz = new boolean[i][i];
    besucht = new boolean[i];
    auf_pfad_besucht = new boolean[i];
  }
  
  public void kante(int i, int j){
    adjazenz[i-1][j-1] = true;
  }
  
  public boolean dfs(int i, String einruecken){
    boolean zyklus=false;
    if (besucht[i-1]) {
      if (auf_pfad_besucht[i-1]) {
        return true;
      } // end of if
    } // end of if
    else {
      System.out.println(einruecken+i);
      besucht[i-1]=true;
      auf_pfad_besucht[i-1]=true;
      
      for (int j=1; j<=anzahl ; j++) {
        if (adjazenz[i-1][j-1]) {
          zyklus = zyklus | dfs(j, einruecken+" ");
        } // end of if
      } // end of for
      auf_pfad_besucht[i-1]=false;
    } // end of if-else
    return zyklus;
  }
  
  public static void main(String[] args){
    Graph g = new Graph(5);
    g.kante(1,2);
    g.kante(2,3);
    g.kante(3,1);
    g.kante(1,4);
    g.kante(4,5);
    if (g.dfs(1,"")) System.out.println("Zyklus");
    else System.out.println("kein Zyklus") ;
  }
}