Depth First Search using Adjacency List | Graph traversal


Depth first search explores on a single path in a graph as long as it find undiscovered vertices. When an edge leads to the discovered vertices it backtrack to the previous vertex and explores along the edge where it find undiscovered vertices. Finally it backtracks to the source vertex from where it started.

Initially all the vertices are white and when a vertex is discovered it becomes gray and then black when it is finished or processed.

Depth First Search Depth First Search

First source vertex 1 is discovered so it becomes gray. Then vertex 4 is discovered. Since there are no vertex after vertex 4 on that path so vertex 4 is processed or finished and it becomes black. Then vertex 2 is discovered and so on. When vertex 3 is processed, control backtracks to the previous vertex which is 2.

Implementation

To store the color of the current vertex, we need a data structure.

Here is the implementation of the function depth_first_search and depth_first_search_visit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

enum Color {WHITE, GRAY, BLACK};
   struct Vertex
   {
      int id;
      Color color;
      Vertex(int _id) : id(_id),
                        color(Color::WHITE)
                        {}
   };

void depth_first_search()
{
   for (const auto& u: vertices)
   {
      if (vertices[u.id].color == WHITE)
      {
         depth_first_search_visit(u.id);
      }
   }
}

void depth_first_search_visit(int u)
{
   vertices[u].color = GRAY;
   std::cout << vertices[u].id <<" ";
   const auto& v = adjacent[u].head;
      if (vertices[v->dest_id].color == WHITE)
      {
         depth_first_search_visit(v->dest_id);
      }
   vertices[u].color = BLACK;
}

Variable color in struct Vertex stores color for the given vertex.

The time complexity of Depth First Search is O(n+m) where n is the number of vertices and m is the number of edges.


Here is the C++ Implementation for Depth First Search using Adjacency List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include <iostream>
#include <vector>

class Graph
{
   int vertex_count;
   enum Color {WHITE, GRAY, BLACK};

   struct Vertex
   {
      int id;
      Color color;
      Vertex(int _id) : id(_id),
                        color(Color::WHITE)
                        {}
   };

   struct Adj_list_node
   {
      int dest_id;
      Adj_list_node * next;
      Adj_list_node(int _dest_id) : dest_id(_dest_id),
                                    next (nullptr)
                                    {}
   };

   struct Adj_list
   {
      Adj_list_node *head;
   };

   std::vector<Vertex> vertices;
   std::vector<Adj_list> adjacent;

public:
   Graph(int);
   void add_edge(int, int);
   void depth_first_search();

 private:
   void depth_first_search_visit(int);
};

Graph::Graph(int v)
{
   vertex_count = v;
   adjacent.resize(vertex_count);

   for (int i = 0; i < vertex_count; i++)
   {
       vertices.push_back( Vertex(i) );
       adjacent[i].head = nullptr;
   }
}

void Graph::depth_first_search()
{
   for (const auto& u: vertices)
   {
      if (vertices[u.id].color == WHITE)
      {
         depth_first_search_visit(u.id);
      }
   }
}

void Graph::depth_first_search_visit(int u)
{
   vertices[u].color = GRAY;
   std::cout << vertices[u].id <<" ";
   const auto& v = adjacent[u].head;
      if (vertices[v->dest_id].color == WHITE)
      {
         depth_first_search_visit(v->dest_id);
      }
   vertices[u].color = BLACK;
}

void Graph::add_edge(int src, int dest)
{
   Adj_list_node *node = new Adj_list_node(dest);
   if (adjacent[src].head == nullptr)
   {
      adjacent[src].head = node;
   }
   else
   {
      Adj_list_node *tmp = adjacent[src].head;
      while (tmp->next != nullptr)
             tmp = tmp->next;

      tmp->next = node;
   }

   //undirected graph
   node = new Adj_list_node(src);
   if (adjacent[dest].head == nullptr)
   {
      adjacent[dest].head = node;
   }
   else
   {
     Adj_list_node *tmp = adjacent[dest].head;
     while (tmp->next != nullptr)
            tmp = tmp->next;

     tmp->next = node;
   }
}

int main()
{
   Graph grp(4);
   grp.add_edge(0, 1);
   grp.add_edge(1, 2);
   grp.add_edge(2, 3);
   grp.add_edge(2, 1);
   grp.add_edge(0, 3);
   grp.depth_first_search();
   std::cout << "\n";
}

Get this post in pdf - Depth First Search

Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy
Competitive Programmer’s Handbook - Antti Laaksonen

You may also like
C++: Dijkstra’s Algorithm using STL
C++: Bellman Ford Algorithm using STL
Breadth First Search using Adjacency List