Depth First Search (DFS) Program in C

By | March 11, 2014
In this tutorial you will learn about Depth First Search (DFS) program in C with algorithm.

Most of graph problems involve 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).
It is like tree. Traversal can start from any vertex, say Vi . 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 (DFS) Algorithm


Depth First Search (DFS) Traversal of a Graph [Algorithm and Program]

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

Depth First Search (DFS) Program in C [Adjacency Matrix]


C Program to implement DFS traversal on a graph represented using an adjacency matrix

Depth First Search (DFS) Program in C [Adjacency List]

C Program to implement DFS traversal on a graph represented using an adjacency list
If you found anything incorrect or have doubts regarding above Depth First Search (DFS) program in C tutorial then comment below.

12 thoughts on “Depth First Search (DFS) Program in C

  1. Varsha Patil

    void DFS(int i)
    node *p;
    In this function after while loop is terminated how the backtracking is happen?

  2. hira naz

    i 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

    1. Andres Rodriguez

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

  3. Zaid Hameed

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

  4. Ankit


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

  5. shubham sharma

    it is for undirected graph but replacing (0,1) with (1,0) gives different to resolve that.

  6. Andrew

    In 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.


Leave a Reply

Your email address will not be published. Required fields are marked *