In DFS, the nodes being explored are stored in a stack data structure. The edges that direct us to unexplored nodes are called ‘discovery edges‘ while the edges going to lead already visited nodes are called ‘block edges‘. DFS is useful in scenarios when a programmer wants to find connected components or cycles in a graph.
Follow this article’s guidelines to implement DFS in C++.
Implementation of DFS in C++
In the following section, we’ll go over how DFS is implemented in C++. One can follow the given steps to implement DFS.
- Insert the root node of a tree or graph into the stack.
- Add the stack’s top item to your visited list.
- Discover all the adjacent nodes to the visited node and add those nodes that have not yet visited the stack.
- Repeat steps 2 and 3 until the stack is empty.
DFS Pseudocode
The DFS pseudocode is shown below. In the init() function, we execute our DFS function on each node. Because the graph may have two disconnected parts, we can run the DFS algorithm on each node to ensure that we have covered every vertex.
a.visited = true
for every b ∈ g.Adj[a]
if b.visited == false
DFS(g,b)
init()
{
For every a ∈ g
a.visited = false
For every a ∈ g
DFS(g, a)
}
Here g, a and b represent the graph, first visited node and node in the stack respectively.
Implementing DFS in C++
A C++ program for DFS implementation is given below:
#include<map>
#include<list>
using namespace std;
template<typename t>
class DepthFirstSearch
{
private:
map<t,list<t> > adjList;
public:
DepthFirstSearch(){}
void Add_edge(t a, t b,bool dir=true)
{
adjList[a].push_back(b);
if(dir)
{
adjList[b].push_back(a);
}
}
void Prnt()
{
for(auto i:adjList){
cout<<i.first<<"->";
for(t entry:i.second){
cout<<entry<<",";
}
cout<<endl;
}
}
void dfs_helper(t node,map<t,bool> &visited){
visited[node] = true;
cout << node <<" " << endl;
for(t neighbour : adjList[node]){
if(!visited[neighbour]){
dfs_helper(neighbour,visited);
}
}
}
void DFS(t src)
{
map<t,bool> visited;
dfs_helper(src,visited);
}
};
int main(){
DepthFirstSearch<int> g;
g.Add_edge(0,5);
g.Add_edge(0,7);
g.Add_edge(4,7);
g.Add_edge(7,8);
g.Add_edge(2,1);
g.Add_edge(0,6);
g.Add_edge(2,4);
g.Add_edge(3,2);
g.Add_edge(3,6);
g.Add_edge(7,5);
g.Add_edge(5,8);
g.Prnt();
g.DFS(6);
cout << endl;
}
In this code, we have implemented DFS algorithm following the pseudo code given above. We have 12 pairs of nodes. We defined a class “G” which represents a graph having vertices a and b that represent visited and unvisited nodes.
Output
Conclusion
DFS is a popular search algorithm useful for several scenarios, such as finding the cycles in a graph, and getting information about the connected components or all vertices in a graph. We also described the working of the DFS method with an example. DFS employs stacks to execute the technique and can also be used on trees.
