C++ Search Algorithms: Depth-First Search and Breadth-First Search

In computer science, search algorithms are essential tools for solving problems related to graphs, trees, and other structures. The two fundamental search strategies are Depth-First Search (DFS) and Breadth-First Search (BFS). This article will provide a detailed introduction to these two algorithms and demonstrate them using C++ code.

1. Depth-First Search (DFS)

1.1 Overview

Depth-First Search is a method used to traverse or search through a tree or graph. It starts from a given node and explores each branch as deeply as possible until it finds the target node or cannot proceed further. It then backtracks to the previous node and attempts to explore other unvisited nodes.

1.2 Characteristics

• Implemented using a stack structure
• Typically implemented recursively
• Backtracks after reaching the deepest level
• Follows the Last In, First Out (LIFO) principle

1.3 Example Code

The following is an example of Depth-First Search implemented in C++:

#include <iostream>
#include <vector>
using namespace std;
class Graph {
    int V; // Number of vertices
    vector<vector<int>> adj; // Adjacency list
public:
    Graph(int v) : V(v) {
        adj.resize(V);
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // Add this line for undirected graphs, not needed for directed graphs
    }
    void DFSUtil(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        for (int i : adj[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }
    void DFS(int start) {
        vector<bool> visited(V, false);
        DFSUtil(start, visited);
    }
};
int main() {
    Graph g(5); // Create a graph with 5 vertices
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    cout << "Depth-First Traversal starting from 0: ";
    g.DFS(0);
    return 0;
}

Explanation:

In this code, we define a <span>Graph</span> class to represent the graph, which includes an adjacency list <span>adj</span>. The method to add edges is <span>addEdge()</span>, while the <span>DFS()</span> method is used to initiate the depth-first traversal. Starting from a given vertex, it accesses and prints each visited node by calling the recursive function <span>DFSUtil()</span>.

2. Breadth-First Search (BFS)

2.1 Overview

Breadth-First Search is a method for accessing trees or graphs in a level-wise manner. It first visits the starting node, then sequentially visits all adjacent nodes at the same level (i.e., nodes at the same distance), and finally delves into the next level until the entire component is covered.

2.2 Characteristics

• Implemented using a queue structure
• Expands all nodes in the current level that have been visited, rather than diving deeper
• Follows the First In, First Out (FIFO) principle

2.3 Example Code

The following is an example of Breadth-First Search implemented in C++:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class GraphBFS {
public:
   int V; // Number of vertices
   vector<vector<int>> adj; // Adjacency list
   GraphBFS(int v) : V(v) {
        adj.resize(V);
    }
   void addEdge(int u, int v) {
       adj[u].push_back(v);
       adj[v].push_back(u);
    }
   void BFS(int start) {
       vector<bool> visited(V, false);
       queue<int> q;
       visited[start] = true;
       q.push(start);
       while (!q.empty()) {
           int node = q.front();
           cout << node << " ";
           q.pop();
           for (int i : adj[node]) {
               if (!visited[i]) {
                   q.push(i);
                   visited[i] = true;
               }
           }
       }
   }
};
int main() {
    GraphBFS gbfs(5);
    gbfs.addEdge(0, 1);
    gbfs.addEdge(0, 2);
    gbfs.addEdge(1, 3);
    gbfs.addEdge(1, 4);
    cout << "Breadth-First Traversal starting from 0: ";
    gbfs.BFS(0);
    return 0;
}

Explanation:

In this implementation, we define another class called <span>GraphBFS</span>, which is similar to the previous DFS class but uses a queue instead of a stack to adhere to the FIFO characteristic. The edges added in the main function are the same as before, and it performs a breadth-first exploration starting from the specified vertex and prints the results.

3. Summary Comparison

Feature	Depth-First Search (DFS)	Breadth-First Search (BFS)
Data Structure	Stack	Queue
Traversal Order	Continues along the path until a termination state is found	Expands level by level
Space Complexity	O(h), where h is the maximum height	O(w), where w is the maximum width
Application Scenarios	Topological sorting, connected component identification	Shortest path finding

From the above comparison, it is evident that both algorithms have their unique features and applicable scenarios. Depending on specific needs, one can choose the appropriate type of problem-solving solution. I hope the information provided in this article helps you understand these two important algorithms in C++ and enriches your programming practice.