Introduction
Depth First Search (DFS) is a fundamental algorithm used in graph theory to explore nodes and edges of a graph. It is a technique that starts at the root node and explores as far as possible along each branch before backtracking. In this article, we will delve into how to write a C++ Program to Implement Depth First Search (DFS) with detailed explanations and real-world examples. By the end of this article, you will have a comprehensive understanding of DFS and how to apply it in C++ projects.
Prerequisites
Before diving into the implementation of Depth First Search, it is important to have a basic understanding of the following concepts:
- Graph Theory: Understanding of graphs, vertices, and edges.
- C++ Programming: Familiarity with C++ syntax, classes, and the Standard Template Library (STL).
- Recursion: Basic knowledge of recursive function calls and their stack behavior.
Ensure you are comfortable with these concepts to fully grasp the implementation of DFS.
1. Understanding Depth First Search
1.1 What is Depth First Search?
Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking. This approach ensures that all nodes are visited in depthward motion, making it useful for pathfinding and cycle detection.
1.2 Why Use Depth First Search?
DFS is particularly useful for problems that require exploring all possibilities, such as:
- Finding connected components in a graph.
- Detecting cycles in a graph.
- Solving puzzles and games (like mazes and Sudoku).
- Pathfinding and topological sorting.
1.3 How Depth First Search Works
- Start at the root (or any arbitrary node in the graph).
- Explore each branch fully before backtracking.
- Mark each node visited to avoid cycles.
- Repeat until all nodes are visited.
2. Implementing Depth First Search in C++
Let’s go through three different examples to understand the implementation and usage of DFS in C++.
2.1 Basic Implementation
In this example, we will implement the basic structure of DFS to traverse a graph.
Code
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
int V; // Number of vertices
list<int> *adj; // Adjacency list
void DFSUtil(int v, vector<bool> &visited);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void DFS(int v); // DFS traversal
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, vector<bool> &visited) {
visited[v] = true;
cout << v << " ";
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v) {
vector<bool> visited(V, false); // Mark all the vertices as not visited
DFSUtil(v, visited); // Call the recursive helper function to print DFS traversal
}
int main() {
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);
cout << "Depth First Traversal (starting from vertex 2): ";
g.DFS(2);
return 0;
}
Output
Depth First Traversal (starting from vertex 2): 2 0 1 3
Explanation
In this example, we implement the basic structure of DFS to traverse a graph. The Graph class contains methods to add edges and perform DFS. The DFSUtil function recursively visits nodes, ensuring each node is visited once. The output shows the traversal order starting from vertex 2.
2.2 DFS to Detect a Cycle in a Graph
In this example, we will extend the implementation to detect cycles in a graph using DFS.
Code
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
int V; // Number of vertices
list<int> *adj; // Adjacency list
bool DFSUtil(int v, vector<bool> &visited, vector<bool> &recStack);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
bool isCyclic(); // Returns true if there is a cycle
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w); // Add w to v’s list.
}
bool Graph::DFSUtil(int v, vector<bool> &visited, vector<bool> &recStack) {
if (!visited[v]) {
visited[v] = true;
recStack[v] = true;
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i] && DFSUtil(*i, visited, recStack))
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // Remove the vertex from recursion stack
return false;
}
bool Graph::isCyclic() {
vector<bool> visited(V, false);
vector<bool> recStack(V, false);
for (int i = 0; i < V; i++)
if (DFSUtil(i, visited, recStack))
return true;
return false;
}
int main() {
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);
if (g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Output
Graph contains cycle
Explanation
In this example, we extend the DFS implementation to detect cycles in a graph. The isCyclic method checks each vertex using the DFSUtil function, which tracks visited nodes and nodes in the current recursion stack. If a node is revisited within the same recursion stack, a cycle is detected. The output confirms the presence of a cycle in the graph.
2.3 DFS for Connected Components in an Undirected Graph
In this example, we will use DFS to find all connected components in an undirected graph.
Code
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
int V; // Number of vertices
list<int> *adj; // Adjacency list
void DFSUtil(int v, vector<bool> &visited);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void connectedComponents(); // Find and print all connected components
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w); // Add w to v’s list.
adj[w].push_back(v); // Add v to w’s list (because the graph is undirected)
}
void Graph::DFSUtil(int v, vector<bool> &visited) {
visited[v] = true;
cout << v << " ";
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::connectedComponents() {
vector<bool> visited(V, false);
for (int v = 0; v < V; v++) {
if (!visited[v]) {
DFSUtil(v, visited);
cout << "\n";
}
}
}
int main() {
Graph g(5); // 5 vertices in graph
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Following are connected components:\n";
g.connectedComponents();
return 0;
}
Output
Following are connected components:
0 1
2 3 4
Explanation
In this example, we use DFS to find all connected components in an undirected graph. The connectedComponents method iterates over all vertices, and for each unvisited vertex, it calls DFSUtil to explore and print all vertices in that connected component. The output shows the connected components in the graph.
Conclusion
Depth First Search (DFS) is a powerful algorithm for exploring and analyzing graphs. Understanding and implementing DFS in C++ can significantly enhance your ability to solve complex graph problems, such as finding connected components, detecting cycles, and pathfinding.