Depth First Search (DFS) Technique in C++
Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
It uses a stack data structure, either explicitly or implicitly through recursion, to keep track of the vertices to be visited next.
DFS can be used to solve various problems such as finding connected components, topological sorting, and detecting cycles in graphs.
C++ Implementation of DFS
// Import necessary libraries #include <iostream> #include <list> #include <vector> using namespace std; /** * Class to represent a graph using an adjacency list representation. */ class Graph { int V; // Number of vertices list<int> *adj; // Pointer to an array containing adjacency lists public: /** * Constructor to initialize the graph with the given number of vertices. * * @param V Number of vertices */ Graph(int V); /** * Method to add an edge to the graph. * * @param v Source vertex * @param w Destination vertex */ void addEdge(int v, int w); /** * Recursive function used by DFS. * * @param v The starting vertex * @param visited Vector to keep track of visited vertices */ void DFSUtil(int v, vector<bool>& visited); /** * Method to perform DFS traversal starting from vertex v. * * @param v The starting vertex */ void DFS(int v); }; /** * Constructor to initialize the graph with the given number of vertices. */ Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } /** * Method to add an edge to the graph. */ void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } /** * Recursive function used by DFS. */ void Graph::DFSUtil(int v, vector<bool>& visited) { // Mark the current node as visited and print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent to this vertex for (auto i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i]) { DFSUtil(*i, visited); } } } /** * Method to perform DFS traversal starting from vertex v. */ void Graph::DFS(int v) { // Mark all the vertices as not visited vector<bool> visited(V, false); // Call the recursive helper function to print DFS traversal DFSUtil(v, visited); } /** * Main method to test the DFS algorithm. */ 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 << "Following is Depth First Traversal starting from vertex 2:" << endl; g.DFS(2); return 0; }
Explanation
The above program demonstrates the Depth First Search (DFS) algorithm in C++:
- Graph Class: The
Graph
class represents a graph using an adjacency list representation. It has methods to add edges and perform DFS. - DFSUtil Method: This is a recursive method used by the
DFS
method to visit nodes. It marks the current node as visited, prints it, and then recursively visits all adjacent vertices that have not been visited yet. - DFS Method: This method initializes the visited array and calls the
DFSUtil
method to start the traversal from the given starting vertex. - Main Method: This is the entry point of the program where a graph is created, edges are added, and the DFS traversal is initiated starting from vertex 2.
In the main method, we create a graph with 4 vertices and add edges between them. The DFS traversal starts from vertex 2 and prints the nodes in the order they are visited.