Applications of Depth First Search | DSA in C++ - Software Development PDF Download

Introduction

Depth First Search (DFS) is a fundamental algorithm used in graph traversal and is a crucial topic in Data Structures and Algorithms (DSA). It is used to explore or traverse all the nodes of a graph in a systematic manner. In this article, we will delve into the applications of Depth First Search and provide easy-to-understand examples and code snippets in C++.

What is Depth First Search?

Applications of Depth First Search

Graph Traversal

DFS can be used to traverse or search a graph to visit all the vertices or nodes. It is especially useful for traversing unweighted or weighted graphs that represent relationships between different entities.

Finding Connected Components

DFS can help find connected components in a graph. A connected component is a subset of nodes in a graph where each node is reachable from every other node in that subset. By performing DFS on a graph, we can identify all the connected components present in it.

Detecting Cycles in a Graph

DFS can also be used to detect cycles in a graph. A cycle is a path in a graph that starts and ends at the same vertex. By keeping track of visited nodes during DFS, we can identify if a cycle exists in the graph.

Implementation of Depth First Search in C++

To implement Depth First Search in C++, we can use either an adjacency list or an adjacency matrix to represent the graph. The algorithm generally involves using a recursive function or a stack to traverse the graph.

Code Examples and Explanation

Example 1: Depth First Traversal

#include <iostream>

#include <vector>

using namespace std;

// Depth First Traversal function

void DFS(vector<vector<int>>& graph, int vertex, vector<bool>& visited) {

    visited[vertex] = true;

    cout << vertex << " ";

    for (int neighbor : graph[vertex]) {

        if (!visited[neighbor]) {

            DFS(graph, neighbor, visited);

        }

    }

}

// Main function

int main() {

    int numNodes, numEdges;

    cout << "Enter the number of nodes: ";

    cin >> numNodes;

    cout << "Enter the number of edges: ";

    cin >> numEdges;

    vector<vector<int>> graph(numNodes);

    vector<bool> visited(numNodes, false);

    cout << "Enter the edges (node1 node2):\n";

    for (int i = 0; i < numEdges; i++) {

        int node1, node2;

        cin >> node1 >> node2;

        graph[node1].push_back(node2);

        graph[node2].push_back(node1);

    }

    int startVertex;

    cout << "Enter the starting vertex: ";

    cin >> startVertex;

    cout << "Depth First Traversal: ";

    DFS(graph, startVertex, visited);

    return 0;

}

Code Explanation:

• The 'DFS' function implements Depth First Traversal using recursion.
• The 'visited' vector keeps track of visited nodes.
• The function starts at the specified 'startVertex', marks it as visited, and prints it.
• It then recursively visits all the unvisited neighbors of the current vertex.

Output:

Enter the number of nodes: 6

Enter the number of edges: 7

Enter the edges (node1 node2):

0 1

0 2

1 3

2 3

3 4

4 5

5 2

Enter the starting vertex: 0

Depth First Traversal: 0 1 3 2 5 4

Example 2: Finding Connected Components

#include <iostream>

#include <vector>

using namespace std;

void DFS(vector<vector<int>>& graph, int vertex, vector<bool>& visited) {

    visited[vertex] = true;

    cout << vertex << " ";

    for (int neighbor : graph[vertex]) {

        if (!visited[neighbor]) {

            DFS(graph, neighbor, visited);

        }

    }

}

int findConnectedComponents(vector<vector<int>>& graph, int numNodes) {

    vector<bool> visited(numNodes, false);

    int components = 0;

    for (int i = 0; i < numNodes; i++) {

        if (!visited[i]) {

            cout << "Connected Component " << components + 1 << ": ";

            DFS(graph, i, visited);

            components++;

            cout << endl;

        }

    }

    return components;

}

int main() {

    int numNodes, numEdges;

    cout << "Enter the number of nodes: ";

    cin >> numNodes;

    cout << "Enter the number of edges: ";

    cin >> numEdges;

    vector<vector<int>> graph(numNodes);

    vector<bool> visited(numNodes, false);

    cout << "Enter the edges (node1 node2):\n";

    for (int i = 0; i < numEdges; i++) {

        int node1, node2;

        cin >> node1 >> node2;

        graph[node1].push_back(node2);

        graph[node2].push_back(node1);

    }

    int numComponents = findConnectedComponents(graph, numNodes);

    cout << "Total connected components: " << numComponents << endl;

    return 0;

}

Code Explanation:

• The 'findConnectedComponents' function finds all the connected components in the graph using DFS.
• It keeps track of visited nodes and increments the 'components' counter whenever a new component is encountered.
• The function prints each connected component by calling the 'DFS' function from the starting vertex of each unvisited component.

Output:

Enter the number of nodes: 7

Enter the number of edges: 5

Enter the edges (node1 node2):

0 1

1 2

2 3

4 5

6 5

Connected Component 1: 0 1 2 3

Connected Component 2: 4 5 6

Total connected components: 2

Sample Problems with Solutions

Let's look at a couple of sample problems that can be solved using DFS.

Problem 1: Finding the Number of Islands

Given a 2D grid consisting of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

// Function to count the number of islands

int countIslands(vector<vector<char>>& grid) {

    // Implement DFS to mark visited islands

}

int main() {

    vector<vector<char>> grid = {

        {'1', '1', '1', '1', '0'},

        {'1', '1', '0', '1', '0'},

        {'1', '1', '0', '0', '0'},

        {'0', '0', '0', '0', '0'}

    };

    int numIslands = countIslands(grid);

    cout << "Number of islands: " << numIslands << endl;

    return 0;

}

Problem 2: Finding a Path in a Maze

Given a maze represented by a 2D grid, find a path from the starting position to the destination. The maze can contain obstacles represented by '1's, while open paths are represented by '0's.

// Function to find a path in a maze

bool findPath(vector<vector<int>>& maze, int row, int col) {

    // Implement DFS to explore the maze and find a path

}

int main() {

    vector<vector<int>> maze = {

        {0, 1, 0, 0, 0},

        {0, 1, 0, 1, 0},

        {0, 0, 0, 1, 0},

        {0, 1, 0, 0, 0},

        {0, 0, 0, 0, 0}

    };

    bool pathExists = findPath(maze, 0, 0);

    cout << "Path exists: " << (pathExists ? "Yes" : "No") << endl;

    return 0;

}

Conclusion

Depth First Search is a powerful algorithm used in various applications of data structures and algorithms. By understanding the concepts and implementation of DFS in C++, you can explore and solve many graph-related problems efficiently. Experiment with different scenarios and practice solving sample problems to reinforce your understanding of DFS.