# Depth First Search Algorithm C Program

By | October 1, 2016

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

1. Push or Insert the starting vertex on the stack.
2. Pop or Delete a vertex from the stack.
3. 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.
4. 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

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

## 3 thoughts on “Depth First Search Algorithm C Program”

1. Vinay Pathak

Thanks for explaining the depth first search algorithm in C. It is so easy to understand.

2. Mayank Rathor

One important point worth mentioning is that the traversing always starts from the Root node.

3. Sumit Sharma

Can we solve Depth First Search using Linked List?