C Program To Implement Depth First Search Algorithm using Stack
Learn How To Traverse a Graph using Depth First Search Algorithm in C Programming. This code for Depth First Search in C Programming makes use of Adjacency Matrix and Stack. The given C program for DFS using Stack is for Traversing a Directed graph, visiting the vertices that are only reachable from the starting vertex.
Must Read: C Program To Implement Stack Data Structure
What is Depth First Search Algorithm?
Depth First Search is a traversal algorithm is used for traversing a graph. A given path is traversed as long as there is no dead end. Once a dead end is reached, previous vertex is checked for unvisited vertices using Backtracking Algorithm.
Algorithm for Depth First Search using Stack and Adjacency Matrix
During the course of the depth first search algorithm, the vertices of the graph will be in one of the two states – visited or initial. Initially, all the vertices are set to initial state. The state of a vertex changes to visited when it is popped from the stack. Initially, the stack is empty.
- Push or Insert the starting vertex on the stack.
- Pop or Delete a vertex from the stack.
- If the deleted vertex is in the initial state, then visit it and change its state to visited. Push all the unvisited vertices adjacent to the popped vertex.
- Repeat steps 2 and 3 until stack is empty.
There is no restriction or compulsion on the order in which the successors of a given vertex are visited. We can, therefore, insert the successors of any vertex in any order.
Must Read: C Program To Implement Bellman Ford Algorithm
C Program For Depth First Search Algorithm using Adjacency Matrix and Stack
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include<stdlib.h> #include<stdio.h> #define MAX 100 #define initial 1 #define visited 2 void graph_traversal(); void DFS(int vertex); void make_graph(); void push(int vertex); int pop(); int isEmpty(); int stack[MAX]; int top = -1; int vertices; int adjacent_matrix[MAX][MAX]; int vertex_status[MAX]; int main() { make_graph(); graph_traversal(); return 0; } void graph_traversal() { int vertex; for(vertex = 0; vertex < vertices; vertex++) { vertex_status[vertex] = initial; } printf("Enter Starting Vertex for DFS:\t"); scanf("%d", &vertex); DFS(vertex); printf("\n"); } void DFS(int vertex) { int count; push(vertex); while(!isEmpty()) { vertex = pop(); if(vertex_status[vertex] == initial) { printf("%3d", vertex); vertex_status[vertex] = visited; } for(count = vertices - 1; count >= 0; count--) { if(adjacent_matrix[vertex][count] == 1 && vertex_status[count] == initial) { push(count); } } } } void push(int vertex) { if(top == (MAX - 1)) { printf("Stack Overflow\n"); return; } top = top + 1; stack[top] = vertex; } int pop() { int vertex; if(top == -1) { printf("Stack Underflow\n"); exit(1); } else { vertex = stack[top]; top = top - 1; return vertex; } } int isEmpty() { if(top == -1) { return 1; } else { return 0; } } void make_graph() { int count, maximum_edges, origin_vertex, destination_vertex; printf("Enter total number of vertices:\t"); scanf("%d", &vertices); maximum_edges = vertices * (vertices - 1); for(count = 0; count < maximum_edges; count++) { printf("Enter Edge [%d] Co-ordinates [-1 -1] to Quit\n", count + 1); printf("Enter Origin Vertex Point:\t"); scanf("%d", &origin_vertex); printf("Enter Destination Vertex Point:\t"); scanf("%d", &destination_vertex); if((origin_vertex == -1) && (destination_vertex == -1)) { break; } if(origin_vertex >= vertices || destination_vertex >= vertices || origin_vertex < 0 || destination_vertex < 0) { printf("Edge Co - ordinates are Invalid\n"); count--; } else { adjacent_matrix[origin_vertex][destination_vertex] = 1; } } } |
Must Read: C Program To Implement Dijkstra’s Algorithm using Adjacency Matrix
Output
Applications of DFS Algorithm
- Finding bridge in a graph
- Topological sorting
- Maze generation
- Finding biconnectivity in graphs
In case you get any Compilation Errors or any doubts in this C Program For Depth First Search Algorithm for Traversal of a Graph, let us know about it in the Comment Section below. Find more details about this algorithm on Wikipedia.
Thanks for explaining the depth first search algorithm in C. It is so easy to understand.
One important point worth mentioning is that the traversing always starts from the Root node.
Can we solve Depth First Search using Linked List?
can you please do it for weighted graph