In this tutorial, you will learn about Depth First Search in C with the algorithm and program examples.

Most graph problems involve the traversal of a graph. Traversal of a graph means visiting each node and visiting exactly once. There are two types of traversal in graphs i.e. Depth First Search (DFS) and Breadth First Search (BFS).

Also Read: Breadth First Search in C

It is like a tree. Traversal can start from any vertex, say V_{i}. Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS. Since a graph can have cycles. We must avoid revisiting a node. To do this, when we visit a vertex V, we mark it visited. A node that has already been marked as visited should not be selected for traversal. Marking of visited vertices can be done with the help of a global array visited[ ]. Array visited[ ] is initialized to false (0).

## Depth First Search Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 |
n ← number of nodes Initialize visited[ ] to false (0) for(i=0;i<n;i++) visited[i] = 0; void DFS(vertex i) [DFS starting from i] { visited[i]=1; for each w adjacent to i if(!visited[w]) DFS(w); } |

The graph shown above is taken as input in both the programs mentioned below.

## Depth First Search Program in C [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 |
#include<stdio.h> void DFS(int); int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10] void main() { int i,j; printf("Enter number of vertices:"); scanf("%d",&n); //read the adjecency matrix printf("\nEnter adjecency matrix of the graph:"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&G[i][j]); //visited is initialized to zero for(i=0;i<n;i++) visited[i]=0; DFS(0); } void DFS(int i) { int j; printf("\n%d",i); visited[i]=1; for(j=0;j<n;j++) if(!visited[j]&&G[i][j]==1) DFS(j); } |

## Depth First Search Program in C [Adjacency List]

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 |
#include<stdio.h> #include<stdlib.h> typedef struct node { struct node *next; int vertex; }node; node *G[20]; //heads of linked list int visited[20]; int n; void read_graph(); //create adjacency list void insert(int,int); //insert an edge (vi,vj) in te adjacency list void DFS(int); void main() { int i; read_graph(); //initialised visited to 0 for(i=0;i<n;i++) visited[i]=0; DFS(0); } void DFS(int i) { node *p; printf("\n%d",i); p=G[i]; visited[i]=1; while(p!=NULL) { i=p->vertex; if(!visited[i]) DFS(i); p=p->next; } } void read_graph() { int i,vi,vj,no_of_edges; printf("Enter number of vertices:"); scanf("%d",&n); //initialise G[] with a null for(i=0;i<n;i++) { G[i]=NULL; //read edges and insert them in G[] printf("Enter number of edges:"); scanf("%d",&no_of_edges); for(i=0;i<no_of_edges;i++) { printf("Enter an edge(u,v):"); scanf("%d%d",&vi,&vj); insert(vi,vj); } } } void insert(int vi,int vj) { node *p,*q; //acquire memory for the new node q=(node*)malloc(sizeof(node)); q->vertex=vj; q->next=NULL; //insert the node in the linked list number vi if(G[vi]==NULL) G[vi]=q; else { //go to end of the linked list p=G[vi]; while(p->next!=NULL) p=p->next; p->next=q; } } |

If you found anything incorrect or have doubts regarding the above DFS program in C then comment below.

Varsha Patilvoid DFS(int i)

{

node *p;

printf("n%d",i);

p=G[i];

visited[i]=1;

while(p!=NULL)

{

i=p->vertex;

if(!visited[i])

DFS(i);

p=p->next;

}

}

In this function after while loop is terminated how the backtracking is happen?

L4_liginThis has only one loop man

mohammad farokhow to solve dfs for greedy.

hira nazi am trying to work with adjacency matrix method in C# but I am unable to use NOT operator with int data type. Can you please elaborate it in C# especially the if condition used in the adjacency matrix's program dfs function

Andres Rodriguezhira naz instead of using an array of ints you just replace it with an array of boolean types and that is it.

Zaid HameedI am trying to compile this program but it shows [Error] 'malloc' was not declared in this scope. any solution plz?

sagar agarwaladd stdlib.h in the header file. it should work.

AnkitHello,

Can we find loop in the graph by using above implementation with adj matrix? Please guide about that.

shubham sharmait is for undirected graph but replacing (0,1) with (1,0) gives different answer.how to resolve that.

jagesh maharjanThank you so much.

Jerlin Angel S.MI need greedy depth first search algorithm program using dot net

jairamhow to check whether the graph is connected or not in dfs.

Narendra Kumar1.mark all the vertices as not visited.

2.apply DFS for graph from any vertix.

3.if any vertix is not visited then return false

4.reverse the graph and mark all the vertices as not visited

5.apply DFS for reversed graph with from same vertix as in step 2

6.if any vertix is not visited then return false

7.return true

AndrewIn your “Depth First Search (DFS) Program in C [Adjacency List]” code the loop on line 57 looks wrong. You initialize G[0] to NULL and then begin inserting all the edges before you finish initializing the rest of G[]. Since you use the variable ‘i’ for both loops you win not continue where you left off, which doesn’t matter since you already inserted the edges. The problem would be if you have less edges than nodes, you may actually delete some edges in your adjacency-list.

abiwo“q=(node*)malloc(sizeof(node));” this is eror in dev c++ whatshal i

do

AdminJust add stdlib.h header file as we have used malloc() function in the program.

mohanwe are not getting the output for this programme

leecode is producing wrong output.. it is not dfs.

AlexAre you sure you understand what DFS does? We start and vertex 0, and we travel on the edge to vertex 1. From vertex 1 we follow the left most edge to the last vertex of the branch which is vertex N. Once all edges leading from Vertex N that lead to an undiscovered vertex are marked. We travel back to the previous vertex which is vertex N-1 of the branch. And continue this method until we are back at vertex 0 and we are done when all edges from Vertex 0 are marked as being discovered.

AlexI would suggest reviewing what Depth First Search is actually doing. The output is correct for Depth First Search

RahulI guess it should be for(j=i;j<n;j++)

DFS(int i)

{

int j;

printf("\n%d",i);

visited[i]=1;

for(j=0;j<n;j++)

if(!visited[j]&&G[i][j]==1)

vardhanno ,that’s correct, if we give the the starting index as other than ‘0’ then we have to start from i=0; every time

jakwhy do I feel like the resulting traversal is wrong?

shouldnt it be 01527634 since after visiting 5,(where 5 is adjacent to 1, 2 and 7), then it will push 2 into stack because its still not visited

Varun kamaniWhat if there is character input data instead of an integer.

here you took an integer so you can do this so by visited[i]=1.

What is there is Character??

dyutithanks

mehedithis code has error

poojanprogramme output is a wrong

ShyamkantExcellent minimum line code. After many years I have used some C code. I have tried it for 9 nodes entered 81 elements and at last all get disappeared. I have tried this two times and get realized that getch() is remaining. After inserting this line I could see the output. Then I have converted it to VB.net for my use. I am sure it will be very great help for me. Thanks a lot.

mysteriouswhy the path is different in two cases.in adjancency matrix there is one path and in adjancey list there is another

tomimolwhy is that if i give the edges in different order( still the same edges) i get a different path / result every time?