C++ Program to Implement Depth-First Search (DFS) In a Graph

1. Introduction

Depth-First Search (DFS) is a fundamental graph traversal technique that explores nodes as profoundly as possible along each branch before backtracking. It is extensively used in numerous applications, from detecting cycles in graphs to topological sorting. In this post, we'll walk you through a basic implementation of DFS in C++.

2. Program Overview

Our program will:

1. Define a Graph class that represents an undirected graph using an adjacency list.

2. The Graph class will have functions to:

- Add an edge to the graph.

- Perform DFS traversal from a given starting vertex.

3. Demonstrate DFS traversal in the main program.

3. Code Program

#include<iostream>
#include<list>
using namespace std;

class Graph {
    int V;  // Number of vertices
    list<int> *adj;  // Pointer to an array containing adjacency lists

    // Recursive function for DFS
    void DFSUtil(int v, bool visited[]) {
        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);
            }
        }
    }

public:
    // Constructor
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

    // Add an edge to the graph
    void addEdge(int v, int w) {
        adj[v].push_back(w);  // Add w to v’s list
    }

    // DFS traversal
    void DFS(int v) {
        // Mark all vertices as not visited
        bool *visited = new bool[V];
        for(int i = 0; i < V; i++) {
            visited[i] = false;
        }

        // Call the recursive function
        DFSUtil(v, visited);
    }
};

int main() {
    Graph g(4);  // Create a graph with 4 vertices
    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:" << endl;
    g.DFS(2);

    return 0;
}

Output:

Depth First Traversal starting from vertex 2:
2 0 1 3

4. Step By Step Explanation

1. The Graph class represents an undirected graph using an adjacency list.

2. We use a list from the STL to manage the adjacency list for each vertex.

3. The DFSUtil is a recursive function that uses the DFS algorithm to explore all the adjacent vertices of the given vertex.

4. The DFS method initializes a visited array to keep track of visited vertices and calls DFSUtil.

5. In the main function, we create a graph with 4 vertices, add edges to the graph, and then demonstrate DFS starting from vertex 2.