C++ • GRAPH TRAVERSAL Depth-First Search (DFS)

C++ • GRAPH TRAVERSAL

Depth-First Search (DFS)

ALGORITHM

Depth-First Search

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V)

STRUCTURE

Recursion / Stack

C++ Implementation

dfs_graph.cpp

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

class GraphDFS
{
    int V; // Number of vertices
    vector<vector<int>> adj; // Adjacency list
    vector<bool> visited;

    // Helper recursive function for DFS
    void dfsHelper(int curr)
    {
        visited[curr] = true;
        cout << curr << " ";

        for (int neighbor : adj[curr])
        {
            if (!visited[neighbor])
            {
                dfsHelper(neighbor);
            }
        }
    }

public:

    // Constructor
    GraphDFS()
    {
        V = 0;
    }

    // Input function to read graph structure
    void input()
    {
        int E;
        cout << "Enter number of vertices: ";
        cin >> V;
        adj.resize(V);

        cout << "Enter number of edges: ";
        cin >> E;

        cout << "Enter edges (u v for undirected edge):\n";
        for (int i = 0; i < E; i++)
        {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    // Depth-First Search interface function
    void dfs(int startNode)
    {
        visited.assign(V, false);
        cout << "DFS Traversal: ";
        dfsHelper(startNode);
        cout << endl;
    }
};

int main()
{
    GraphDFS obj;

    obj.input();
    
    int start;
    cout << "Enter starting vertex: ";
    cin >> start;

    obj.dfs(start);

    return 0;
}

Sample Input

Enter number of vertices: 5
Enter number of edges: 5
Enter edges (u v for undirected edge):
0 1
0 2
1 3
1 4
2 4
Enter starting vertex: 0

Output

DFS Traversal: 
0 1 3 4 2 

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

#include <vector>

Includes dynamic array support for adjacency list and visited tracking.

class GraphDFS

Creates a class named GraphDFS to encapsulate graph data and traversal methods.

vector<vector<int>> adj;

Adjacency list representation storing neighbors for each vertex.

void dfsHelper(int curr)

Recursive utility function that explores deep down each branch of the graph.

GraphDFS()

Class constructor that initializes vertex count to zero.

void input()

Reads the number of vertices, edges, and connections from the user.

visited.assign(V, false);

Resets and tracks which vertices have already been visited.

visited[curr] = true;

Marks the current node as visited before exploring its neighbors.

dfsHelper(neighbor);

Recursively calls DFS on an unvisited neighbor, diving deeper into the graph.

GraphDFS obj;

Instantiates the GraphDFS object and triggers the constructor.

return 0;

Signals successful program execution.

How Depth-First Search (DFS) works: DFS explores a graph by going as deep as possible along each branch before backtracking. Starting from a chosen vertex, it marks it as visited, prints/processes it, and recursively visits the first unvisited neighbor until it hits a dead end, at which point it backtracks to explore remaining paths.