Depth First Search in C++

Hey Guys ! Hope you are doing well !
In my previous post i wrote about implementation of Adjacency List in C++. So if you don't know how to implement Adjacency List in C++, you must read this post.

---

Depth First Search

DFS (in short) is a simple algorithm to traverse a graph.
Lets understand the logic behind this algorithm with the help of following graph.

Blue > Green > Red

Suppose we start dfs from node 1. We mark it as visited and move to one of its neighbour which is not visited till now. We can see till now neither node 2 nor node 3 is visited. So firstly, we move to node 2. Mark node 2 as visited and similarly move to one of the neighbour of node 2. Neighbours of 2 are 1 and 4 and node 1 is already marked visited, so we move to node 4. Mark node 4 as visited and now we move to node 6 and marked it as visited. But at this point there is no neighbour of node 6 which is not visited. So we move back to node from which we came to node 6 ie. node 4. Now node 4 has one neighbour node 5 which is not visited, So we move node 5 and mark it as visited. Similarly node 5 have no unvisited neighbour. Jump back to node 4. No unvisited neighbours of node 4 so move back to node 2. No unvisited neighbour of node 2 So move back to node 1. Now it has an unvisited neighbour i.e. node 3. So move to node 3 and mark it as visited. Similarly No unvisited neighbours, move back to node 1 and now all vertices are marked visited and we stop at this point.

---

Now i hope after reading this example you got the idea of graph traversal using DFS. So without wasting any time lets see the implementation part.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int n = 100000; // Maximum number of nodes, change according to constraints. map<int, vector<int> > adjList; // Considering undirected graph bool visited[n]; void dfs(int u){ visited[u] = true; for(int i = 0 ; i < adjList[u].size() ; i ++){ int v = adjList[u][i]; // neighbour of u if(visited[v] != true){ // checking if neighbour is already visited or not dfs(v); } } } // inside int main memset(visited, 0, sizeof(visited)); /* * Take inputs and make Adjacency List */ dfs(1); // Let the starting vertex be 1

Complexity:
Adjacency List : O(V + E)
Adjacency Matrix : O(V*V)
where V = Number of vertices, E = Number of edges

---

Some of the applications of DFS :

• Topological sorting.
• Finding connected components.
• Finding the bridges of a graph.
• Finding the articulation points of a graph.
• Finding strongly connected components.
• Finding biconnectivity in graphs.
• Solving puzzles with only one solution, such as mazes.(You can use this in Robot maze solving competitions like in IIT Bombay's TechFest)

I will discuss each of them in detail in my next blog-posts.

This is my third blog-post and I hope you can now implement DFS very easily ! For any doubts you are most welcome and if you find any error in this post please help me correct it.

THE END !