C++ Program for DFS Traversal
In C++ Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. In this article, we will learn how to implement DFS traversal in C++.
Example:
Input:
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
Output:
DFS Traversal: 2 0 1 3
Implementing DFS Traversal in C++
To implement DFS traversal in C++, we use a recursive function that calls itself for every unvisited adjacent node. We start from the root (or any arbitrary node) and mark the node as visited. Then we recursively visit all the vertices adjacent to this node.
Algorithm for DFS Traversal
- Create a graph using an adjacency list.
- Mark all vertices as not visited.
- Use a recursive utility function to perform DFS from a given vertex.
- Mark the current vertex as visited and print it.
- Recursively visit all adjacent vertices that are not yet visited.
- Call the DFS utility function for every vertex to ensure all disconnected vertices are covered.
C++ Program for DFS Traversal
The below example demonstrates how to implement DFS traversal in C++.
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
// Number of vertices
int V;
// Adjacency list to store graph
vector<list<int> > adj;
// Utility function for DFS traversal
void DFSUtil(int v, vector<bool>& visited)
{
// Mark the current node as visited
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this
// vertex
for (int i : adj[v]) {
if (!visited[i])
// Recur for the unvisited adjacent nodes
DFSUtil(i, visited);
}
}
public:
// Constructor to initialize graph with V vertices
Graph(int V)
{
this->V = V;
adj.resize(V);
}
// Function to add an edge to the graph
void addEdge(int v, int w) { adj[v].push_back(w); }
// DFS traversal of the vertices reachable from v
void DFS(int v)
{
// Mark all vertices as not visited
vector<bool> visited(V, false);
// Call the recursive helper function to print DFS
// traversal
DFSUtil(v, visited);
}
};
int main()
{
// Create a graph with 4 vertices
Graph g(4);
// Add edges to the graph
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
// Print the DFS traversal starting from vertex 2
cout << "Depth First Traversal (starting from vertex "
"2): ";
g.DFS(2);
cout << endl;
return 0;
}
Output
Depth First Traversal (starting from vertex 2): 2 0 1 3
Time Complexity: O(V + E) V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V)