C Program for DFS Algorithm using Recursion
Learn How To Implement DFS Algorithm using Recursion in C Programming. This DFS Algorithm in C Programming makes use of Adjacency Matrix and Recursion method.
Must Read: C Program For Implement Prim’s Algorithm To Find MST
What is DFS Algorithm?
DFS Algorithm is an abbreviation for Depth First Search Algorithm. This DFS method using Adjacency Matrix is used to traverse a graph using Recursive method. Any given path in a graph is traversed until a dead end occurs after which backtracking is done to find the unvisited vertices and then traverse them too.
In the recursive algorithm for Depth First Search C Program, we have to take all the three vertex states viz., initial, visited and finished. Initially, all the vertices have its status as initial. When a vertex is visited, its state is changed to visited. The status of a vertex becomes finished when we backtrack from it.
Must Read: C Program To Implement Depth First Search Algorithm using Stack
C Program To Implement DFS Algorithm using Recursion and Adjacency Matrix
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 | #include<stdio.h> #define MAX 100 #define initial 1 #define visited 2 #define finished 3 int vertices; int adjacent_matrix[MAX][MAX]; void make_graph(); void graph_traversal(); void depth_first_search(int vertex); int state[MAX]; int main() { make_graph(); graph_traversal(); return 0; } void graph_traversal() { int vertex; for(vertex = 0; vertex < vertices; vertex++) { state[vertex] = initial; } printf("Enter Initial Vertex for Depth First Search:\t"); scanf("%d", &vertex); depth_first_search(vertex); for(vertex = 0; vertex < vertices; vertex++) { if(state[vertex] == initial) { depth_first_search(v); } } printf("\n"); } void depth_first_search(int vertex) { int count; printf("%3d", vertex); state[vertex] = visited; for(count = 0; count < vertices; count++) { if(adjacent_matrix[vertex][count] == 1 && state[count] == initial) { depth_first_search(count); } } state[vertex] = finished; } void make_graph() { int count, maximum_edges, origin_vertex, destination_vertex, weight; 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 Christofides Algorithm
Output
In case you get any Compilation Errors or any doubts in this C Program For Depth First Search Algorithm using Recursion for Traversal of a Graph, let us know about it in the Comment Section below. Find more about this algorithm on GeeksForGeeks.
Thanks for this DFS Program in C. Finally I got a complete code.
Why have you used %3d in this DFS C program?