Depth-First Search (DFS) is a fundamental algorithm in computer science used for traversing or searching tree or graph data structures. Unlike Breadth-First Search (BFS), which explores nodes level by level, DFS dives deep into the graph, exploring as far as possible along each branch before backtracking. DFS has numerous applications, including pathfinding, cycle detection, and topological sorting.

Program Structure

The C++ program to implement DFS traversal is organized into the following key components:

• Graph Representation: Using an adjacency list to represent the graph.
• DFS Implementation: Utilizing recursion for the traversal process.
• Main Function: Handling user input, constructing the graph, invoking DFS, and displaying the results.

Code Implementation

The following C++ program implements DFS traversal on a graph using an adjacency list representation:

// DFS Traversal of a Graph in C++
// This program performs Depth-First Search (DFS) traversal on a graph.

#include <iostream>
#include <vector>
#include <list&gt>
#include <stack&gt>

using namespace std;

// Class to represent a graph using adjacency list representation
class Graph {
    int V; // Number of vertices
    list *adj; // Pointer to an array containing adjacency lists

public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // Function to add an edge to graph
    void DFS(int s); // Function to perform DFS traversal from a given source s
private:
    void DFSUtil(int v, vector &visited); // Utility function for DFS
};

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

// Function 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
    adj[w].push_back(v); // Since the graph is undirected, add v to w’s list
}

// Utility function for DFS traversal
void Graph::DFSUtil(int v, vector &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 it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            DFSUtil(*it, visited);
        }
    }
}

// Function to perform DFS traversal from a given source s
void Graph::DFS(int s) {
    // Mark all the vertices as not visited
    vector visited(V, false);

    // Call the recursive helper function to print DFS traversal
    DFSUtil(s, visited);
}

int main() {
    int V, E;
    cout << "DFS Traversal of a Graph using C++\n";
    cout << "-------------------------------\n";
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    int start;
    cout << "Enter the starting vertex for DFS traversal: ";
    cin >> start;

    cout << "\nDFS Traversal starting from vertex " << start << ":\n";
    g.DFS(start);
    cout << endl;

    return 0;
}
        

Program Explanation

The program implements DFS traversal on an undirected graph using an adjacency list. Below is a detailed breakdown of its components:

1. Graph Representation

The graph is represented using an adjacency list, which is an efficient way to represent sparse graphs. An adjacency list is an array of lists, where each index of the array represents a vertex, and each element in the list at that index represents an adjacent vertex.

list<int> *adj;

2. Adding Edges

The addEdge function adds an undirected edge between two vertices by adding each vertex to the other’s adjacency list.

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v’s list
    adj[w].push_back(v); // Since the graph is undirected, add v to w’s list
}
        

3. DFS Traversal Function

The DFS function initiates the DFS traversal from a given source vertex. It utilizes a helper function DFSUtil to perform the recursive traversal.

void Graph::DFS(int s) {
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);

    // Call the recursive helper function to print DFS traversal
    DFSUtil(s, visited);
}
        

Function: DFSUtil

This recursive helper function performs the actual DFS traversal. It marks the current vertex as visited, prints it, and recursively visits all adjacent unvisited vertices.

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 it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            DFSUtil(*it, visited);
        }
    }
}
        

4. Main Function

The main function handles user input, constructs the graph by adding edges, and initiates the DFS traversal from the specified starting vertex.

int main() {
    int V, E;
    cout << "DFS Traversal of a Graph using C++\n";
    cout << "-------------------------------\n";
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    int start;
    cout << "Enter the starting vertex for DFS traversal: ";
    cin >> start;

    cout << "\nDFS Traversal starting from vertex " << start << ":\n";
    g.DFS(start);
    cout << endl;

    return 0;
}
        

Program Documentation

Detailed documentation for each component of the program:

Class: Graph

• Purpose: Represents a graph using an adjacency list and provides methods to add edges and perform DFS traversal.
• Members:
  • int V; – Number of vertices in the graph.
  • list<int> *adj; – Pointer to an array of adjacency lists.
• Functions:
  • Graph(int V); – Constructor to initialize the graph with V vertices.
  • void addEdge(int v, int w); – Adds an undirected edge between vertex v and vertex w.
  • void DFS(int s); – Initiates DFS traversal from the specified source vertex s.
  • void DFSUtil(int v, vector<bool> &visited); – Helper function that performs recursive DFS traversal.

Function: addEdge

• Purpose: Adds an undirected edge between two vertices in the graph.
• Parameters:
  • int v – The source vertex.
  • int w – The destination vertex.
• Returns: None.
• Logic:
  1. Add vertex w to the adjacency list of vertex v.
  2. Add vertex v to the adjacency list of vertex w (since the graph is undirected).

Function: DFS

• Purpose: Initiates DFS traversal from a given source vertex.
• Parameters:
  • int s – The starting vertex for DFS traversal.
• Returns: None. Prints the DFS traversal order to the console.
• Logic:
  1. Initializes a visited vector to keep track of visited vertices.
  2. Calls the recursive helper function DFSUtil starting from vertex s.

Function: DFSUtil

• Purpose: Performs the actual DFS traversal recursively.
• Parameters:
  • int v – The current vertex being visited.
  • vector<bool> &visited – Vector to track visited vertices.
• Returns: None. Prints the current vertex to the console.
• Logic:
  1. Marks the current vertex v as visited.
  2. Prints the current vertex.
  3. Recursively visits all adjacent unvisited vertices.

Function: main

• Purpose: Acts as the entry point of the program, handling user input and initiating DFS traversal.
• Parameters: None.
• Returns: 0 upon successful execution.
• Logic:
  1. Prompts the user to enter the number of vertices (V) and edges (E).
  2. Reads each edge’s source and destination vertices and adds them to the graph using the addEdge function.
  3. Prompts the user to enter the starting vertex for DFS traversal.
  4. Calls the DFS function to perform the traversal and displays the order of visited vertices.

How the Program Works

1. User Input: The program begins by asking the user to input the number of vertices (V) and edges (E). It then prompts the user to enter each edge in the format (source destination), which are used to construct the adjacency list.
2. Graph Construction: Using the addEdge function, the program builds the adjacency list representation of the graph, ensuring that each undirected edge is represented in both directions.
3. DFS Traversal: The user is prompted to enter the starting vertex for DFS. The DFS function is then called with this vertex, performing the traversal and printing the order in which vertices are visited.
4. Output: The program outputs the sequence of vertices visited during the DFS traversal, providing a clear view of the traversal order.

Example Execution

Consider the following example input and output:

DFS Traversal of a Graph using C++
-------------------------------
Enter the number of vertices: 5
Enter the number of edges: 4
Enter the edges in the format (source destination):
0 1
0 2
1 3
1 4
Enter the starting vertex for DFS traversal: 0

DFS Traversal starting from vertex 0:
0 1 3 4 2 
        

Explanation: The DFS traversal starts at vertex 0, visits vertex 1, then vertex 3, backtracks to vertex 1, visits vertex 4, and finally visits vertex 2. The traversal order is therefore 0, 1, 3, 4, 2.

Conclusion

Depth-First Search (DFS) is an essential algorithm for traversing and searching through graph structures. This C++ implementation effectively demonstrates DFS traversal using an adjacency list and recursion, ensuring that all vertices are visited in the correct order. Understanding and implementing DFS is crucial for solving various real-world problems, including pathfinding, cycle detection, and topological sorting.