Last Updated on January 2, 2023 by Prepbytes
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.
What is DFS?
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.
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.
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.
How DFS is different from BFS?
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’s see how BFS traversal works using an example.
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.
How DFS works?
Let’s see how DFS traversal works using an example. We will also see a dry run of the example to understand it more clearly.
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’s see further steps of DFS traversal.
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.
Path till now: 1
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.
Path till now: 1 -> 3
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.
Path till now: 1 -> 3 -> 6
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.
Path till now: 1 -> 3 -> 6
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.
Path till now: 1 -> 3 -> 6
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.
Path till now: 1 -> 3 -> 6 -> 2
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.
Path till now: 1 -> 3 -> 6 -> 2 -> 4
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.
Path till now: 1 -> 3 -> 6 -> 2 -> 4
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
Path till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7
.
In 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.
Path till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7
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.
Path till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7
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.
Path till now: 1 -> 3 -> 6 -> 2 -> 4 -> 7 -> 5
C Program of DFS (Depth First Search) in c:
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’s see the pseudo-code of the DFS algorithm.
DFS(graph, node)
node.visited = true
for each neighbor ∈ graph.Adj[node]
If neighbor.visited == false
DFS(graph,neighbor)
main() {
For each node ∈ graph
node.visited = false
For each node ∈ graph
DFS(graph, node)
}Now let’s 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.
// dfs program in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int v);
struct Graph {
int totalVertices;
int* visited;
struct node** adjLists;
};
void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
graph->visited[vertex] = 1;
printf("%d -> ", vertex);
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->totalVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void displayGraph(struct Graph* graph) {
int v;
for (v = 1; v < graph->totalVertices; v++) {
struct node* temp = graph->adjLists[v];
printf("\n%d => ", v);
while (temp) {
printf("%d, ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
printf("\n");
}
int main() {
struct Graph* graph = createGraph(8);
addEdge(graph, 1, 5);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 3, 6);
addEdge(graph, 2, 7);
addEdge(graph, 2, 4);
printf("\nThe Adjacency List of the Graph is:");
displayGraph(graph);
printf("\nDFS traversal of the graph: \n");
DFS(graph, 1);
return 0;
} Output
The Adjacency List of the Graph is:
1 => 3, 2, 5,
2 => 4, 7, 1,
3 => 6, 1,
4 => 2,
5 => 1,
6 => 3,
7 => 2,
DFS traversal of the graph:
1 -> 3 -> 6 -> 2 -> 4 -> 7 -> 5Time Complexity: O(V+E) where V is the number of nodes and E is the number of edges. We have to traverse through all the nodes and edges so the time complexity is O(V+E)
Space Complexity: O(V) because in the worst case we might need to store recursion calls for all the nodes.