When Traversing a Tree/Graph what is the difference between Breadth First and Depth first? Any coding or pseudocode examples would be great.
This question is related to
algorithm
depth-first-search
breadth-first-search
tree-traversal
Given this binary tree:
Breadth First Traversal:
Traverse across each level from left to right.
"I'm G, my kids are D and I, my grandkids are B, E, H and K, their grandkids are A, C, F"
- Level 1: G
- Level 2: D, I
- Level 3: B, E, H, K
- Level 4: A, C, F
Order Searched: G, D, I, B, E, H, K, A, C, F
Depth First Traversal:
Traversal is not done ACROSS entire levels at a time. Instead, traversal dives into the DEPTH (from root to leaf) of the tree first. However, it's a bit more complex than simply up and down.
There are three methods:
1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:
Grab the Root. (G)
Then Check the Left. (It's a tree)
Grab the Root of the Left. (D)
Then Check the Left of D. (It's a tree)
Grab the Root of the Left (B)
Then Check the Left of B. (A)
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)
Check the Right of D. (It's a tree)
Grab the Root. (E)
Check the Left of E. (Nothing)
Check the Right of E. (F, Finish D Tree. Move back to G Tree)
Check the Right of G. (It's a tree)
Grab the Root of I Tree. (I)
Check the Left. (H, it's a leaf.)
Check the Right. (K, it's a leaf. Finish G tree)
DONE: G, D, B, A, C, E, F, I, H, K
2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.
Check the Left of the G Tree. (It's a D Tree)
Check the Left of the D Tree. (It's a B Tree)
Check the Left of the B Tree. (A)
Check the Root of the B Tree (B)
Check the Right of the B Tree (C, finished B Tree!)
Check the Right of the D Tree (It's a E Tree)
Check the Left of the E Tree. (Nothing)
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...
Onwards until...
DONE: A, B, C, D, E, F, G, H, I, K
3) POSTORDER:
LEFT, RIGHT, ROOT
DONE: A, C, B, F, E, D, H, K, I, G
Usage (aka, why do we care):
I really enjoyed this simple Quora explanation of the Depth First Traversal methods and how they are commonly used:
"In-Order Traversal will print values [in order for the BST (binary search tree)]"
"Pre-order traversal is used to create a copy of the [binary search tree]."
"Postorder traversal is used to delete the [binary search tree]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing
I think it would be interesting to write both of them in a way that only by switching some lines of code would give you one algorithm or the other, so that you will see that your dillema is not so strong as it seems to be at first.
I personally like the interpretation of BFS as flooding a landscape: the low altitude areas will be flooded first, and only then the high altitude areas would follow. If you imagine the landscape altitudes as isolines as we see in geography books, its easy to see that BFS fills all area under the same isoline at the same time, just as this would be with physics. Thus, interpreting altitudes as distance or scaled cost gives a pretty intuitive idea of the algorithm.
With this in mind, you can easily adapt the idea behind breadth first search to find the minimum spanning tree easily, shortest path, and also many other minimization algorithms.
I didnt see any intuitive interpretation of DFS yet (only the standard one about the maze, but it isnt as powerful as the BFS one and flooding), so for me it seems that BFS seems to correlate better with physical phenomena as described above, while DFS correlates better with choices dillema on rational systems (ie people or computers deciding which move to make on a chess game or going out of a maze).
So, for me the difference between lies on which natural phenomenon best matches their propagation model (transversing) in real life.
This picture should give you the idea about the context in which the words breadth and depth are used.
Depth-first search algorithm acts as if it wants to get as far away from the starting point as quickly as possible.
It generally uses a Stack
to remember where it should go when it reaches a dead end.
Rules to follow: Push first vertex A on to the Stack
Java code:
public void searchDepthFirst() {
// Begin at vertex 0 (A)
vertexList[0].wasVisited = true;
displayVertex(0);
stack.push(0);
while (!stack.isEmpty()) {
int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
// If no such vertex
if (adjacentVertex == -1) {
stack.pop();
} else {
vertexList[adjacentVertex].wasVisited = true;
// Do something
stack.push(adjacentVertex);
}
}
// Stack is empty, so we're done, reset flags
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}
Applications: Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.
Queue
.Java code:
public void searchBreadthFirst() {
vertexList[0].wasVisited = true;
displayVertex(0);
queue.insert(0);
int v2;
while (!queue.isEmpty()) {
int v1 = queue.remove();
// Until it has no unvisited neighbors, get one
while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
vertexList[v2].wasVisited = true;
// Do something
queue.insert(v2);
}
}
// Queue is empty, so we're done, reset flags
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}
Applications: Breadth-first search first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex.
Hopefully that should be enough for understanding the Breadth-First and Depth-First searches. For further reading I would recommend the Graphs chapter from an excellent data structures book by Robert Lafore.
Source: Stackoverflow.com