{"id":11509,"date":"2022-12-29T10:54:06","date_gmt":"2022-12-29T10:54:06","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11509"},"modified":"2023-01-02T13:18:19","modified_gmt":"2023-01-02T13:18:19","slug":"dfs-program-in-c","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/dfs-program-in-c\/","title":{"rendered":"DFS Program in C"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will learn what is DFS, and how DFS is different from BFS, we will also how DFS works with a dry run of an example, and we will also see how to write a DFS program in c.<\/p>\n

What is DFS?<\/h2>\n

DFS stands for Depth First Search and it is used to traverse all the nodes of the graph. With this technique, first, we pick and node and after that, we traverse through all the possible nodes in that path or branch, and then we will do backtracking.<\/p>\n

Backtracking means when the DFS algorithm reaches a particular node that does not have any neighbors to visit. When it reaches a node that does not have any neighbors after that, it will backtrack to its previous node. Let’s see an example of DFS.<\/p>\n

\"\"<\/p>\n

In the above image, the DFS algorithm will start from the source node which is 1 and it has four neighbors (5, 3, 4, 2) we can choose anyone of them. If we choose 5 then our vised nodes are 1 and 5. Now, 5 does not have any neighbors so we will backtrack to its previous node which is 1 and now 1 has three non-visited neighbors (3, 4, 2). If we choose 3 then our path will become 1,5,3. Now, 3 has one non-visited neighbor(4) so we can choose only that node, and our path becomes 1,5,3,4. Now, 4 does not have any non-visited nodes thus we have to backtrack to the previous node 3 and it also does not have any non-visited neighbors thus we will backtrack to previous node 1, and 1 has only one non-visited node (2). We will go to 2 and our path will become 1,5,3,4,2. So the path becomes 1->5->3->4->2 if we use DFS traversal.<\/p>\n

How DFS is different from BFS?<\/h2>\n

BFS stands for Breadth First Search. In this technique, we traverse through a graph level vise. We need to use the Queue data structure to perform BFS traversal. Let\u2019s see how BFS traversal works using an example.<\/p>\n

\"\"<\/p>\n

In the above example, first, we will traverse through level 1 thus our path will become 1. After that, we will traverse through level 2 and now our path will be 1, 5, 3, 2. Now, we will traverse through level 3 and our new path will become 1, 5, 3, 2, 6, 4, 9. At the last, we will traverse through level 4 and our new path will become 1, 5, 3, 2, 6, 4, 9, 8, 7. If we use the same example for DFS traversal then our path will become 1, 5, 6, 8, 3, 4, 7, 9, 2.<\/p>\n

How DFS works?<\/h2>\n

Let\u2019s see how DFS traversal works using an example. We will also see a dry run of the example to understand it more clearly.<\/p>\n

\"\"<\/p>\n

In the above example, we have taken one graph and have also taken an array to keep track of visited and non-visited nodes and this array is initialized with 0 which means all the nodes are non-visited. In this example, we will start traversing from source node 1. Let\u2019s see further steps of DFS traversal.<\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 1 as visited and we will look for non-visited neighbors. Node 1 has three non-visited neighbors 3, 2, and 5. We can choose anyone out of these three. We will now go for Node 3.
\nPath till now: 1<\/strong><\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 3 as a visited. Node 3 has only one non-visited neighbor 6. Thus, we have the only choice to go for node 6.
\nPath till now: 1 -> 3<\/strong><\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 6 as visited. Node 6 does not have any non-visited neighbors so we need to backtrack to its previous node which is 3.
\nPath till now: 1 -> 3 -> 6<\/strong> <\/p>\n

\"\"<\/p>\n

In this step, node 3 is already visited. Node 3 does not have any non-visited neighbors. Thus, we will backtrack to the previous node of 3 which is 1.
\nPath till now: 1 -> 3 -> 6<\/strong><\/p>\n

\"\"<\/p>\n

In this step, node 1 is already visited. Node 1 has two non-visited neighbors which are 2 and 5. We can choose any one out of these two nodes. We will choose node 2 first.
\nPath till now: 1 -> 3 -> 6<\/strong> <\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 2 as a visited. Node 2 has two non-visited neighbors which are 4 and 7. We can choose any one out of these two. We will go for node 4 first.
\nPath till now: 1 -> 3 -> 6 -> 2<\/strong><\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 4 as visited. Node 4 does not have any non-visited neighbors so we need to backtrack to its previous node which is 2.
\nPath till now: 1 -> 3 -> 6 -> 2 -> 4<\/strong><\/p>\n

\"\"<\/p>\n

In this step, node 2 is already visited. Node 2 has only one non-visited neighbor 7. Thus, we have the only choice to go for node 7.
\nPath till now: 1 -> 3 -> 6 -> 2 -> 4<\/strong> <\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 7 as visited. Node 7 does not have any non-visited neighbors so we need to backtrack to its previous node which is 2
\nPath till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7<\/strong> <\/p>\n

\"\"
\n.
\nIn this step, node 2 is already visited. Node 2 does not have any non-visited neighbors so we need to backtrack to its previous node which is 1.
\nPath till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7<\/strong><\/p>\n

\"\"<\/p>\n

In this step, node 1 is already visited. Node 1 has only one non-visited neighbor which is 5. We can choose only one node which is 5. We will choose node 5.
\nPath till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7<\/strong> <\/p>\n

\"\"<\/p>\n

In this step, first, we will mark node 5 as visited. Node 5 does not have any non-visited neighbors so we need to backtrack to its previous node which is 1. And now 1 also does not have any non-visited neighbors so DFS traversal will end here.<\/p>\n

Path till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7 -> 5<\/strong><\/p>\n

C Program of DFS (Depth First Search) in c:<\/h2>\n

We have already seen what is DFS and how DFS works. Now, We will see how to write the DFS program in c. Before writing the DFS program in c let\u2019s see the pseudo-code of the DFS algorithm.<\/p>\n

DFS(graph, node)\n    node.visited = true\n    for each neighbor \u2208 graph.Adj[node]\n        If neighbor.visited == false\n            DFS(graph,neighbor)\n\nmain() {\n    For each node \u2208 graph\n        node.visited = false\n     For each node \u2208 graph\n       DFS(graph, node)\n}<\/code><\/pre>\n
Now let\u2019s see how to write the DFS program in c using the above algorithm. We will use the same example as above to write the DFS program in c.<\/p>\n\t\t\t\t\t\t