# DFS Algorithm using Recursion C Program

## 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?