1

According to wikipedia, there are basically two difference in implementation of DFS and BFS.

They are:
1)DFS uses stack while BFS uses queue.(this I understand).

2)DFS delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex.

I am not able to understand the second difference.I mean why DFS visits the node after removing from stack while BFS visits the node before adding it to queue.

Thanks!

Extra info:
In a simple implementation of above two algorithms, we take a boolean array (let us name it visited) to keep track of which node is visited or not.The question mentions this visited boolean array.

hoder
  • 257
  • 1
  • 3
  • 14
  • 1
    Where exactly did you read that in Wikipedia? DFS and BFS are fundamentally different algorithms, which cannot be described as something that differs in only two minute details. It has been discussed here many times before. Here's one example http://stackoverflow.com/questions/20429310/why-is-dfs-depth-first-search-claimed-to-be-space-efficient Again, DFS and BFS are two *completely different* algorithms. Replacing FIFO with LIFO in BFS will produce an algorithm that properly reproduces DFS discovery sequence, but it still won't be a true DFS algorithm. – AnT stands with Russia Mar 11 '14 at 18:34
  • @AndreyT http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode – hoder Mar 11 '14 at 19:46
  • 1
    The non-recursive implementation is fake. It is not DFS. It is a major error in Wikipedia article. The non-recursive implementation is what I describe as "pseudo-DFS" at my link above. – AnT stands with Russia Mar 11 '14 at 20:49
  • AnT, would you be able to help me out on this question here? https://stackoverflow.com/questions/70835523/bfs-iterative-dfs-and-recursive-dfs-when-to-mark-node-as-visited – mker Jan 24 '22 at 23:36

2 Answers2

0

The wikipedia article mentions two ways to perform a DFS: using recursion and using a stack.

For completeness, I copy both here:

Using recursion

procedure DFS(G,v):
   label v as discovered
   for all edges from v to w in G.adjacentEdges(v) do
      if vertex w is not labeled as discovered then
         recursively call DFS(G,w)

Using a stack

procedure DFS-iterative(G,v):
   let S be a stack
   S.push(v)
   while S is not empty
      v ← S.pop() 
      if v is not labeled as discovered:
         label v as discovered
         for all edges from v to w in G.adjacentEdges(v) do
            S.push(w)

The important thing to know here is how method calls work. There is an underlying stack, lets call is T. Before the method gets called, it's arguments are pushed on the stack. The method then takes the arguments from that stack again, performs its operation, and pushes its result back on the stack. This result is then taken from the stack by the calling method.

As an example, consider the following snippet:

function caller() {
    callResult = callee(argument1, argument2);
}

In terms of the stack T, this is what happens (schematically):

// inside method caller
T.push(argument1);
T.push(argument2);
"call method callee"

// inside method callee
argument2 = T.pop();
argument1 = T.pop();
"do something"
T.push(result);
"return from method callee"

// inside method caller
callResult = T.pop();

This is pretty much what is happening in the second implementation: the stack is used explicitly. You can compare making the call to DFS in the first snippet with pushing a vertex on the stack, and compare executing the call to DFS in the first snippet with popping the vertex from the stack.

The first thing after popping vertex v from the stack is marking it as discovered. This is equivalent to marking it as discovered as a first step in the execution of DFS.

Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
0

This is probably the first time I ever heard of when DFS would delay setting the "discovered" property until popped from the stack (even on wikipedia, both the recursive and iterative pseudocode have labeling the current node as discovered before pushing the children in the stack). Also, if you "discover" the node only when you finish processing it, I think you could easily get into endless loops.

There are however situations when I use two flags for each node: one set when entering, one upon leaving the node (usually, I write DFS as recursive, so, right at the end of the recursive function). I think I used something like this is when I needed stuff like: strongly connected components or critical points in a connected graph (="nodes which, if removed, the graph would lose its connectivity"). Also, the order in which you exit the nodes is often used for topological sorting (the topological sort is just the inverse of the order you finished processing the nodes).

Catalin Pol
  • 261
  • 1
  • 3