n8118's blog

Bfs using recursion
By n8118, history, 9 years ago, In English

I know how to implement dfs using recursion but i couldn't implement bfs using recursion Can some one help me with the recursion code? Thanks in advance..

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, think about the data structure of BFS and DFS.

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

BFS can't be done by recursion as BFS goes level by level , which can't be done by a recursive function which goes as deep as it can then go back when it ends a path and so on .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Not to be facetious, but you can easily implement BFS using recursion. What you probably mean is "BFS and recursion cannot be combined as naturally as DFS and recursion can be combined". DFS uses a stack to maintain a frontier, and recursion uses (or utilizes) a stack to maintain, well, the 'call stack'. Implementing DFS using recursion simply means replacing the stack with a call stack. Since BFS does not use a stack, there is nothing we can replace with the call stack, and thus this implementation feels a bit unnatural.

    That said, BFS with recursion would sort of look like this:

    void bfs(int n, vector<vector<int>>& edgelist, vector<int>& dist, queue<int>& q) {
    
    for (int i : edgelist[n]) {
        if (dist[i] != -1) continue;
        dist[i] = dist[n] + 1;
        q.push(i);
    }

    if (!q.empty()) {
        n = q.front();
        q.pop();
        bfs(n, edgelist, dist, q);
    }
}

    As you can see, recursion is not an integral part of the algorithm, but is just used to 'loop', really. That said, you'll get stackoverflow errors on moderately sized graphs. So just use an iterative implementation, please.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

you can do the dfs iterative, like the bfs using a stack, but implement a bfs using recursion it is not necessary, because you are increasing the complexity of the method.

And speaking like crazy people, maybe are something like this:

bfs(vector<int>list_of_level){
  if(list_of_level.empty())return;
  vector<int>next_level;
  for(i<list_of_level.size()){
    for(j<graph[list_of_level[i]].size()){
      int node=graph[list_of_level[i]][j];
      if(visit[node])continue;
      visit[node]=true;
      next_level.add(node);
    }
  }
  bfs(next_level);
}
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to calculate the shortest path length between two vertices using Bfs in a graph?? How to print the shortest path?

→ Reply