In one of my previous article I have discussed about the Breadth First Search or commonly known as BFS using C# example. This article will contain one more way of traversing the trees or graphs known as Depth First Search or commonly known as DFS.
What is Depth First Search(DFS)
In DFS algorithm you start with a source node and go in the depth as much as possible. In other words you go and visit all the children in a single branch before moving to other branch.
If we are well known to the Depth First Search it would be very easy to understand system design concepts and crack interview questions.
DFS
- Starts at the source vertex
- Pick one of the not visited neighbor and visits it.
- This process repeats recursively and the recursion repeats into a branch until it cannot go any further.
Below is the sample code snippet to achieve DFS in C#. I have created a tree using the code I have discussed in my previous post.
/* * 1 * / | \ * 2 5 9 * / / \ \ * 3 6 8 10 * / / * 4 7 * */ Graph graph = new Graph(11); graph.AddEdge(1, 2, false); graph.AddEdge(2, 3, false); graph.AddEdge(3, 4, false); graph.AddEdge(1, 5, false); graph.AddEdge(5, 6, false); graph.AddEdge(6, 7, false); graph.AddEdge(5, 8, false); graph.AddEdge(1, 9, false); graph.AddEdge(9, 10, false); graph.DFS(); public class Graph { LinkedList<int>[] linkedListArray; public Graph(int v) { linkedListArray = new LinkedList<int>[v]; } /// <summary> /// The method takes two nodes for which to add edge. /// </summary> /// <param name="u"></param> /// <param name="v"></param> /// <param name="blnBiDir"></param> public void AddEdge(int u, int v, bool blnBiDir = true) { if (linkedListArray[u] == null) { linkedListArray[u] = new LinkedList<int>(); linkedListArray[u].AddFirst(v); } else { var last = linkedListArray[u].Last; linkedListArray[u].AddAfter(last, v); } if (blnBiDir) { if (linkedListArray[v] == null) { linkedListArray[v] = new LinkedList<int>(); linkedListArray[v].AddFirst(u); } else { var last = linkedListArray[v].Last; linkedListArray[v].AddAfter(last, u); } } } internal void DFSHelper(int src, bool[] visited) { visited[src] = true; Console.Write(src + "->"); if (linkedListArray[src] != null) { foreach (var item in linkedListArray[src]) { if (!visited[item] == true) { DFSHelper(item, visited); } } } } internal void DFS() { Console.WriteLine("DFS"); bool[] visited = new bool[linkedListArray.Length + 1]; DFSHelper(1, visited); } }
Lets dissect the above code. I have created a tree data structure for the figure shown in the commented code.
As the nature of DFS, we should go to the depth of each branch before moving to another branch. Starting from the node 1 as the source, the algorithm will traverse the nodes 2, 3 and 4. Finally moving to next branch of node 5.
For branch 5 is also divided in two more branches, the algorithm goes to nodes 6, 7 and finally coming to node 8.
Finally the last branch consisting of the nodes 9 and 10 is traversed.
Moreover as you can see in the code I am doing this recursively in the method DFSHelper. In the code I have kept an array to keep the note of all the nodes visited.
That was for a tree data structure.
DFS for Graphs
Tree data structure is Graph without cycle as we have seen in the above code. Now suppose if we have to traverse a Graph data structure as shown in the comment section of below code snippet, DFS can be used here as well.
/* * 0 ---------- 1 * | | * | | * | | * | | * | | * 4----------3----------- 2 * */ Graph graph = new Graph(5); graph.AddEdge(0, 1); graph.AddEdge(0, 3); graph.AddEdge(1, 2); graph.AddEdge(2, 3); graph.AddEdge(3, 4); graph.DFS(); internal void DFS() { Console.WriteLine("DFS"); bool[] visited = new bool[linkedListArray.Length + 1]; DFSHelper(0, visited); }
The DFSHelper method is same as the previous code snippet. The source node I have taken here is 0. The algorithm will traverse all the nodes starting from node 0 and moving to node 1. It will still go deeper to nodes 2, 3 and 4 unlike BFS where the algorithm first visits all the children nodes.
DFS using Stack
There is an alternate way to implement DFS. In this approach we will use Stack data structure. Since stack uses first in last out approach to handle elements. We will add the adjacent child nodes of a parent node to the stack.
private void DFSHelperWithStack(int src, bool[] visited) { Stack<int> stackForDFS = new Stack<int>(); foreach (var item in linkedListArray[src]) { stackForDFS.Push(item); } visited[src] = true; Console.Write(src + "->"); while (stackForDFS.Count > 0) { if (!visited[stackForDFS.Peek()]) { var item = stackForDFS.Pop(); visited[item] = true; Console.Write(item + "->"); if (linkedListArray[item] != null) { foreach (var child in linkedListArray[item]) { stackForDFS.Push(child); } } } } }
Advantages of DFS:
- Depth-first search on a binary tree generally requires less memory than breadth-first.
- Depth-first search can be easily implemented with recursion.
Disadvantages of DFS:
- A DFS doesn’t necessarily find the shortest path to a node, while breadth-first search does.