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..
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | adamant | 156 |
5 | cry | 155 |
5 | atcoder_official | 155 |
5 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Name |
---|
First, think about the data structure of BFS and DFS.
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 .
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:
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.
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:
How to calculate the shortest path length between two vertices using Bfs in a graph?? How to print the shortest path?
You can find the code here which does that you want: http://e-maxx.ru/algo/bfs keeps nodes ancestor nodes in p and then reconstructs the whole path.