Understanding Depth-First Search (DFS) in Graphs Using C++

Depth-First Search (DFS) is a fundamental graph traversal technique that explores as far as possible along each branch before backtracking. It is widely used in various applications such as detecting cycles, finding connected components, and solving puzzles like mazes. This blog provides a detailed walkthrough of implementing DFS in C++.

Code Overview

Here’s a step-by-step explanation of the code that implements DFS for an undirected graph represented as an adjacency matrix.

1. Graph Representation

The graph is represented as an adjacency matrix:

• The matrix graph is a 2D array of size N × N, where N is the number of vertices.

• graph[i][j] = 1 indicates a direct edge between vertices i and j.

• graph[i][j] = 0 means there is no edge.

2. DFS Traversal Function

The function dfs_print is a recursive implementation of DFS.

void dfs_print(int** graph, int N, int starting_vertex, int* visited){
    cout << starting_vertex << endl;
    visited[starting_vertex] = 1;
    for(int i=0;i<N;i++){
        if(i == starting_vertex) continue;
        if(graph[starting_vertex][i] && !visited[i]){
            dfs_print(graph, N, i, visited);
        }
    }
}

Key Steps:

1. Print and Mark Visited: The current vertex is printed, and visited[starting_vertex] is set to 1 to avoid revisiting.

2. Recursive Exploration: The function checks all adjacent vertices (graph[starting_vertex][i] == 1) that haven’t been visited. For each unvisited vertex, it makes a recursive call to dfs_print.

3. Input and Initialization

The main function begins by reading the number of vertices (N) and edges (E).

int N, E;   
cin >> N >> E;

Graph Initialization:

• The adjacency matrix graph is dynamically allocated and initialized to 0, indicating no edges initially.

int** graph = new int*[N];
for(int i=0;i<N;i++){
    graph[i] = new int[N];
    for(int j=0;j<N;j++)
        graph[i][j] = 0;
}

Input Edges:

• The graph edges are read, and the adjacency matrix is updated to represent connections.

for(int i=0;i<E;i++){
    int a, b;
    cin >> a >> b;
    graph[a][b] = graph[b][a] = 1;
}

Visited Array:

• A 1D array visited is initialized to 0, marking all vertices as unvisited.

int* visited = new int[N];
for(int i=0;i<N;i++) visited[i] = 0;

4. Performing DFS

The DFS traversal starts at the vertex 0.

dfs_print(graph, N, 0, visited);

This ensures that all reachable vertices from 0 are visited and printed in depth-first order.

5. Cleaning Up

Dynamic memory allocated for graph and visited is freed to avoid memory leaks.

delete[] visited;
for(int i=0;i<N;i++) delete[] graph[i];
delete[] graph;

Sample Input and Output

Input:

5 6
0 1
0 2
1 3
1 4
3 4
2 3

• 5 vertices (N=5)

• 6 edges (E=6)

• Edge list: (0-1), (0-2), (1-3), (1-4), (3-4), (2-3)

Output:

0
1
3
4
2

Understanding the Output

• The traversal starts at the vertex 0.

• From 0, it moves to 1, then to 3, then to 4. After backtracking, it explores 2.

Time Complexity

• Adjacency Matrix Representation:

  • The DFS traversal takes O(N^2), where N is the number of vertices, because for each vertex, it checks all other vertices to find edges.

Space Complexity

• Visited Array: O(N)

• Recursive Stack: In the worst case (skewed graph), the recursion depth can be O(N)

Applications of DFS

• Cycle Detection: DFS can detect cycles in both directed and undirected graphs.

• Connected Components: Identify distinct connected components in a graph.

• Topological Sorting: Used in directed acyclic graphs (DAGs).

• Pathfinding: Useful for solving mazes and puzzles.

Conclusion

This implementation of DFS using an adjacency matrix in C++ demonstrates the power and simplicity of the depth-first traversal algorithm. While adjacency matrices are straightforward for dense graphs, adjacency lists can be more space-efficient for sparse graphs. Understanding DFS is fundamental for solving complex graph problems in competitive programming and real-world applications.

Happy coding! 🚀

References

1. Find the code for the above explanation here.