Depth-first search uses LIFO/Stack. Breadth-first search uses FIFO/Queue. What does a recursive algorithm use? A combination of both?
Asked
Active
Viewed 1,051 times
1
-
1Recursion uses the (call) stack. – meowgoesthedog Jul 05 '17 at 10:17
-
https://stackoverflow.com/questions/33703019/breadth-first-traversal-of-a-tree-in-javascript/33704700#33704700 – Matt Timmermans Jul 05 '17 at 11:53
-
you've got it backwards: stack is FIFO, queue is LIFO. – Will Ness Jul 05 '17 at 14:16
-
Can BFS even be executed w/ recursion? I had thought it was only possible through iteration. – jbuddy_13 May 23 '22 at 14:12
1 Answers
2
a recursive algorithm always use Depth-first Search (DFS)
Pseudocode
Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered
A recursive implementation of DFS:
1 procedure DFS(G,v):
2 label v as discovered
3 for all edges from v to w in G.adjacentEdges(v) do
4 if vertex w is not labeled as discovered then
5 recursively call DFS(G,w)
Ziggy192
- 75
- 6