C Program To Implement Depth First Search

Depth First search algorithm is used for traversing or searching the graph.  Select a vertex as start vertex V and mark it as visited.  Any non-visited vertex w adjacent to V is selected and apply depth first search to w.  If a vertex x is reached and all its adjacent vertices are already visited, then we need to back track to the last visited vertex which has any non-visited vertex w adjacent to it and apply depth first search on w.  This process continues until no more non-visited vertex can be selected from any of the visited vertices.

Algorithm For Depth First Search:
DFS (v) {
visited[v] = 1
for all w adjacent to v do
if  visited[v] == 0
                        DFS(w)
}

We are going to do depth first search for the below graph.
                   +-------------------- V1 -----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+   +-------------------- V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +-------------------   V6  ----------------------+

Steps to perform Depth First Search:

• Select a start vertex and mark it as visited.  Vertex v1 is selected and it is marked as visited.
• V1 has two adjacent vertices.  We need to select one among V2 and V3.  Let's consider that we will always select lowest vertex(v2 < v3 <=> 2 < 3).  So, vertex V2 is selected.
• V1 and V4 are adjacent to V4.  Select V4 since V1 is already visited.
• V6 is selected.
• V4, V5, V2 and V3 are adjacent to V6.  V2 and V4 are already visited.  So, we cannot select them.  (V3 < V5) Mark V3 as visited.
• V5 is the only non-visited vertex.  So, select it and mark it as visited.

So, the given graph is visited in the order: V1, V2, V4, V6, V3 and V5.
                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+   +-------------------- V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------  V6  ----------------------+

Adjacency list representation of the input graph:

• There's one list for each vertex in the graph.  Each list has a head node(V1, V2, V3, V4, V5 & V6).
• Adjacent vertices are linked to the head node.  And the head node provides random access to any particular vertex(by using data in the node as vertex).

+----------+        +---------+        +----------+
| V1        |----->|  2  |    |----->|  3  |  N  |
|            |        +---------+        +----------+
+----------+        +---------+        +----------+        +----------+
|            |----->|  1  |     |---->|  4  |      |----->|  6  |  N  |
| V2        |        +---------+        +----------+        +----------+
+----------+       +---------+         +----------+        +----------+
|            |---->|  1  |     |----->|  5  |      |----->|  6  |  N  |
| V3        |       +---------+         +----------+        +----------+
+----------+       +---------+         +----------+
|            |---->|  2  |     |----->|  6  | N   |
| V4        |       +---------+         +----------+
+----------+       +---------+        +----------+ 
|            |---->|  3  |     |----->|  6  |  N  |
| V5        |       +---------+        +----------+
+----------+       +---------+         +----------+         +----------+         +----------+
|            |---->|  2  |     |----->|  3  |      |------>|  4  |  N  |----->|  5  |  N  |
| V6        |       +---------+         +----------+         +----------+         +----------+
+----------+

See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search

Example Program To Implement Depth First Search(in C):

---

  #include <stdio.h>
  #include <stdlib.h>

  #define VERTEXCOUNT 6
  #define VISITED 1

  struct node {
        int data;
        struct node *next;
  };

  int visitVertex[VERTEXCOUNT];

  struct node * createNode(int data) {
        struct node *newnode;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = NULL;
        return newnode;
  }

  void depthFirstSearch(int index, struct node *vertex[]) {

        struct node *temp;

        /* mark the unvisted node as visited and print it to console */

        visitVertex[index - 1] = VISITED;

        temp = vertex[index - 1];

        printf("VV(Visited Vertex): %d\n", index);

        while (temp != NULL) {

                /*

                 * if current vertex is already visited,

                 * try next adjacent vertex.  Otherwise, do

                 * depth first search for current vertex.

                 */

                if (visitVertex[temp->data - 1] == VISITED)

                        temp = temp->next;

                else

                        depthFirstSearch(temp->data, vertex);

        }

  }

  void deleteNodes(struct node *myNode) {

        struct node *temp;

        while (myNode != NULL) {

                temp = myNode;

                myNode = myNode->next;

                free(temp);

        }

  }

  int main() {

        struct node *vertex[VERTEXCOUNT], *newnode;

        int index = 0;

        /* Create adjacency list for the graph */

        newnode = createNode(2);

        vertex[0] = newnode;

        newnode->next = createNode(3);

        newnode = createNode(1);

        vertex[1] = newnode;

        newnode->next = createNode(4);

        newnode->next->next = createNode(6);

        newnode = createNode(1);

        vertex[2] = newnode;

        newnode->next = createNode(5);

        newnode->next->next = createNode(6);

        newnode = createNode(2);

        vertex[3] = newnode;

        newnode->next = createNode(6);

        newnode = createNode(3);

        vertex[4] = newnode;

        newnode->next = createNode(6);

        newnode = createNode(2);

        vertex[5] = newnode;

        newnode->next = createNode(3);

        newnode->next->next = createNode(4);

        newnode->next->next->next = createNode(5);

        /* depth first search operation */

        depthFirstSearch(1, vertex);

        while (index < VERTEXCOUNT) {

                deleteNodes(vertex[index]);

                index++;

        }

        return 0;

  }

  Output: (C Program To Implement Depth First Search)

  jp@jp-VirtualBox:~/$ ./a.out
  VV(Visited Vertex): 1
  VV(Visited Vertex): 2
  VV(Visited Vertex): 4
  VV(Visited Vertex): 6
  VV(Visited Vertex): 3
  VV(Visited Vertex): 5