Breitensuche in Graph rekursiv

[JeremiahTheBard]

Hallo,
wollt fragen, wie man die Breitensuche in einem Graphen rekursiv umsetzt.
Hier meine iterative Version:

  public boolean Breitensuche (GraphNode start, GraphNode ende){
    Queue schlange = new Queue();
    schlange.push(start);
    start.mark();
    while(!schlange.isEmpty()){
      GraphNode temp = schlange.pop();
      if(temp==ende) return true;
      Liste list = getNeighbours(temp);
      for(int i=0;i<list.size();i++){
         if(!list.get(i).isMarked()){
        schlange.push(list.get(i));
        }
      }
    }
  return false;
  }

Die rekursive Umsetzung will mir einfach nich einfallen. Für Tipps wäre ich sehr dankbar.

 

[JeremiahTheBard]

ok ich hab die iterative Version verbessert, sodass man an dem Rückgabewert den schnellsten Weg von A nach B erkennen kann:

  public String Breitensuche (GraphNode start, GraphNode ende){
    String result = "";
    Queue schlange = new Queue();
    schlange.push(start);
    result+=start.getName();
    start.mark();
    while(!schlange.isEmpty()){
      GraphNode temp = schlange.pop();
      if(temp==ende) return result;
      Liste list = getNeighbours(temp);
      for(int i=0;i<list.size();i++){
        if(!list.get(i).isMarked()){
        schlange.push(list.get(i));
        result+=temp.getName()+"-"+list.get(i).getName();
        }
      }
    }
  return result;
  }

Bei der rekursiven Version bin ich aber immer noch nich weitergekommen, bitte helft mir :bahnhof:

 

[frankyv]

Hallo Jeremiah

Warum brauchst du denn die rekursive Version?
Deine Version mit der Queue ist doch gut.

Gruß