Depth-First-Search short tutorial
In this story, I will be teaching one of the most important algorithms, Depth-First-Search, namely DFS, and showing some examples of how to use it.
First, let’s get into the definition of DFS. DFS starts at the root node(the starting node) and explores as far as possible before backtracking. In simple words, it searches to the deepest level and come back to the top and search for the second deepest level.
In the example graph above, let say we want to search for the number 12. If we apply a DFS, and assume 1 is the root node, the search will go 1->2->3->4 and then back track to 3 and explore 5. After that, it will backtrack to 2 and explore 6. Now it has explored the part of tree illustrated below.
Now our algorithm will backtrack to 1 and visit 7. After this step, we backtrack to 1 and we have the remaining nodes left as shown below. Now try to write down the sequence of nodes visited on your own and check back when you are done.
Solution: 1->8->9->10, backtrack to 9->11, backtrack to 8->12, which is the number we wanted to search for.
Hopefully, now you have a basic understanding of the DFS on a binary search tree. Now we will move to a slightly more complicated problem: applying DFS on a weighted directional graph.
The DFS is commonly used in graphs like this in the field of artificial intelligence and understand the steps is crucial for a good foundation of AI methods. The number on the edges here are weights. Now before jumping to the problem, we need to define an important concept in AI: fringe.
fringe: a data structure used to store all the possible states (nodes) that you can go from the current states.
Since this problem is more complicated than the simple binary search tree, I will be using a more systematic approach to solve it. We will need to first write a list of current nodes and use a priority queue for the fringe.
When we first start the problem, our current node is N/A and the fringe is S(start). Below each node, we need to write done the depth of this node because algorithms like DFS depends on the depth as it wants to go to the deepest node before backtracking. In the beginning, we have {S(0)} as it takes 0 steps to get to the starting node in the fringe.
Now we pop our element in the fringe to the current node. From our current node S, we can go to the nodes A, B, C. Thus, in this step, our current node is S(0) and fringe is {A(1), B(1), C(1)}. Since all of the nodes in the fringe has the same depth, we will go by alphabetical order and pop A(1) as our next current node.
From A(1), we can explore E, and we add E(2) to our fringe. Now, the fringe is {B(1), C(1), E(2)} and since we are using DFS, it will pop the element with the highest depth, which is E(2) as our next current node. Now this problem has become very easy, so try to solve it(i.e. find a path to the goal using DFS) before reading the solution below.
SOLUTION: we then go from E(2) to D(3) and D(3) to GOAL(4) and we pop GOAL(4) as the current state. The path is S->A->E->D->GOAL. A more detailed solution is shown below.
Now as you have already read through the problem, try to mimic the whole solution on your own and check back if you have any questions.
Note: The DFS only looks at the depth level, and it ignores the weight. I purposefully wrote the weight on the graph to confuse you (or make you remember :))
DFS is a very important algorithms along with other algorithms like BFS, A*, etc.. Read my other articles about BFS and how it compares and contrast with DFS.
