1. In General:
The key difference between depth first search and breadth first search is the the order of visiting each nodes in a graph.
In breadth first search, we start at a node, called root, visiting its all immediate neighbors before moving to another node. After moving to another node, we also trying ti discover all of its neighbors and so on. In other words, we are trying to go as WIDE as possible. We keep doing this until we have no node left to visit.
In depth first search, however, we start at a node and traverse as far as possible along the branch before recursing back to the original node. In other words, we are trying to go as DEEP as possible from the root.
2. Implementation
Implementation-wise, the breadth first search uses a queue to keep track of the nodes visited. Depth first search, on the other hand uses a stack.
In depth first search, we mark a node as visited when we pop it from the stack, NOT when we push it into the stack..
Suppose we have a graph:
If we mark the nodes as visited when we pop it from the stack:
1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v ← S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w)
The order of the nodes we visit will be: A B D H E C F G. Note that we push the node into the stack from right to left (We push C before B and push E before D).
However, if we mark the node as visited when we push it into the stack as the following code:
1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 label v as discovered 5 while S is not empty 6 v ← S.pop() 7 if v is not labeled as discovered: 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w) 10 label w as discovered
The order of nodes visited will be: A C B E D H G F, which is not depth first search.
This is a big difference from breadth first search: Whether we mark a node as visited when we push that node into the queue or when we remove from the queue doesn’t matter. This time we push the node into the queue from left to right.
1 procedure BFS(G,v): 2 let Q be a Queue 3 Q.enqueue(v) 4 while Q is not empty 5 v ← Q.dequeue() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 Q.enqueue(w)
The order of visiting is: A B C D E G F H
Note: Depth first search has a recursive implementation, which implicitly use a stack.
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)
In this implementation, we only mark a node as visited when we start exploring its neighbors, which is equivalent to the non recursive version.
