Tuesday, 28 May 2013

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        |       +---------+         +----------+         +----------+         +----------+
+----------+

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



No comments:

Post a Comment