# Breitensuche in Graph rekursiv



## JeremiahTheBard (30. Nov 2013)

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 (30. Nov 2013)

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 (30. Nov 2013)

Hallo Jeremiah

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

Gruß


----------

