C++ Coding Test Course, DFS and BFS Programs

1. DFS (Depth First Search) Algorithm

DFS is one of the algorithms for traversing graphs, also known as depth-first search. It starts from a vertex of the graph and continues to explore deeper into adjacent vertices. When no further depth can be explored, it returns to the last visited vertex to explore other adjacent vertices.

1.1 Characteristics of DFS

• Can be easily implemented using a stack or recursion.
• Visits every vertex once, so the time complexity is O(V + E), where V is the number of vertices and E is the number of edges.
• Requires additional memory to store information about visited vertices during execution.

1.2 Implementation of DFS

                
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << ' ';

            for (int i = adj[node].size() - 1; i >= 0; --i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}
                
            

2. BFS (Breadth First Search) Algorithm

BFS is one of the algorithms for traversing graphs, also known as breadth-first search. It starts from a vertex of the graph and visits all adjacent vertices first before progressing deeper.

2.1 Characteristics of BFS

• Implemented using a queue.
• Visits every vertex once, so the time complexity is O(V + E).
• Suitable for finding the shortest path.

2.2 Implementation of BFS

                
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(int start, vector &visited, const vector> &adj) {
    queue q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';

        for (int i = 0; i < adj[node].size(); ++i) {
            if (!visited[adj[node][i]]) {
                visited[adj[node][i]] = true;
                q.push(adj[node][i]);
            }
        }
    }
}
                
            

3. Problem: Graph Traversal (Application of DFS and BFS)

Problem description: Write a program to count the number of connected components in a given disconnected graph. Given the vertices and edges of the graph, use DFS and BFS algorithms to explore the sets of connected vertices and calculate the number of connected components.

3.1 Input Format

The first line will contain the number of vertices N (1 <= N <= 1000) and the number of edges M (1 <= M <= 100,000). The following M lines will contain the edge information.

3.2 Output Format

Output the number of connected components.

3.3 Example

                
Input:
5 3
1 2
2 3
4 5

Output:
2
                
            

3.4 Solution Process

This problem can be solved by using both DFS and BFS algorithms to count the number of connected components.

1. Represent the graph in the form of an adjacency list.
2. Initialize a visited array to record visited vertices.
3. Iterate through each vertex; every time an unvisited vertex is found, use DFS or BFS to visit all vertices included with that vertex.
4. Increase the count every time a connected component is found and finally print the count.

3.5 C++ Code Example

                
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;

            for (int i = 0; i < adj[node].size(); ++i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> adj(N + 1);
    vector visited(N + 1, false);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Add in both directions for undirected graph.
    }

    int componentCount = 0;

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            DFS(i, visited, adj);
            componentCount++;
        }
    }

    cout << componentCount << endl;
    
    return 0;
}