Блог пользователя n8118

Bfs using recursion
Автор n8118, история, 9 лет назад, По-английски

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..

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 .

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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);
}
→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить