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.

Depth First Search Algorithm in C Programming using Adjacency Matrix and Stack

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

C Program For Depth First Search Algorithm using Adjacency Matrix and Stack

 

Must Read: C Program To Implement Dijkstra’s Algorithm using Adjacency Matrix

Output

C Program For Depth First Search Algorithm using Adjacency Matrix and Stack

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.

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

    Reply
  2. Mayank Rathor

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

    Reply

Let's Discuss