C++ Coding Test Course, Breadth-First Search

Hello everyone! Today, I will explain the Breadth-First Search (BFS) algorithm, which often appears in coding tests. In this lecture, we will explore the fundamental concepts of BFS and solve a sample algorithm problem using it.

What is BFS?

Breadth-First Search (BFS) is one of the algorithms used to explore nodes in graph theory. BFS starts from one node, explores all adjacent nodes, and then explores adjacent nodes in the next step. This allows us to solve shortest path problems or calculate the shortest distance.

Characteristics of BFS

  • Uses Queue data structure: BFS employs a queue data structure to store nodes to be explored.
  • Guarantees shortest path: BFS guarantees the shortest path in graphs with uniform weights.
  • Levels are explored in order: BFS explores each level sequentially, so it searches from nearby nodes to distant nodes.

Problem Description

Now let’s look at a simple problem utilizing BFS.

Problem: 01-Calculating Shortest Distance Using Breadth-First Search

Write a program that calculates the shortest distance from a specific starting node to all other nodes in a given undirected graph. The input includes the number of nodes in the graph, the number of edges, and the two nodes of each edge.

Input Format

The first line contains the number of nodes N (1 ≤ N ≤ 10^5) and the number of edges M (1 ≤ M ≤ 2 * 10^5).
The next M lines represent the two nodes u, v (1 ≤ u, v ≤ N) of each edge.
The last line gives the starting node S.

Output Format

Output the shortest distance to each node, separated by spaces.
If a node is not connected, output -1.

Solution Process

Let’s take a step-by-step look at how to solve the problem using BFS.

Step 1: Graph Representation

We will use an adjacency list to represent the graph. The adjacency list stores the other nodes connected to each node in a list format. This allows efficient memory usage.

Step 2: Implementing BFS

BFS explores adjacent nodes using a queue. The exploration order is as follows:

  1. Insert the starting node into the queue and initialize the distance to 0.
  2. Remove a node from the queue and check all nodes adjacent to that node.
  3. If the explored node is unvisited, set its distance to the current node’s distance + 1 and insert it into the queue.
  4. Repeat this process until the queue is empty.

Step 3: Writing the Code

Now, based on the above process, let’s write the C++ code.


#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
vector graph[MAX_N + 1];
int dist[MAX_N + 1];

void bfs(int start, int n) {
    queue q;
    fill(dist, dist + n + 1, -1);  // Initialize distances
    dist[start] = 0;                // Set distance for the start node
    q.push(start);                   // Insert start node into the queue

    while(!q.empty()) {
        int current = q.front();
        q.pop();
        
        for(int neighbor : graph[current]) {
            if(dist[neighbor] == -1) { // Unvisited node
                dist[neighbor] = dist[current] + 1;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int N, M, S;
    cin >> N >> M;
    
    for(int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);         // Add undirected edge
        graph[v].push_back(u);
    }
    cin >> S;

    bfs(S, N); // Call BFS

    for(int i = 1; i <= N; ++i) {
        cout << dist[i] << " ";       // Output distances
    }
    cout << endl;

    return 0;
}

Step 4: Executing the Code and Results

By executing the above code, we calculate and output the shortest distance from the starting node S to each node. For example, if the following input is given:

Input Example:

6 7
1 2
1 3
2 4
3 4
4 5
4 6
5 6
1

Output Example:

0 1 1 2 3 2

Step 5: Conclusion

In this lecture, we explored the Breadth-First Search (BFS) algorithm, which often appears in C++ coding tests. BFS is useful for solving shortest path problems and can be applied to various challenges. By thoroughly understanding and utilizing this algorithm, you can achieve good results in coding tests.

I hope this lecture has been helpful for your job preparation. Thank you!