C++ Coding Test Course, Pathfinding

In this course, we will implement an algorithm to find paths in graphs using C++.
In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search).
During this process, we will solve problems that frequently appear in actual coding tests, and
we will explain the algorithm theory and implementation in detail.

Problem Description

You need to solve the problem of finding the shortest path between two points in a given graph.
The graph consists of nodes and edges, with each node being connected to others.
This problem is generally provided in the following format: 

    Input:
    6 7
    0 1
    0 2
    1 3
    1 4
    2 5
    4 5
    3 5
    0 5

    Output:
    2

The first line indicates the number of nodes (vertices) and the number of edges,
while the subsequent lines represent the connection information for each edge.
The last line signifies the start and end nodes.

Algorithm Theory

Pathfinding in graphs can be performed using two methods: DFS (Depth-First Search) and BFS (Breadth-First Search).
In this course, we will focus on finding the shortest path using BFS.
BFS operates intuitively, proceeding by exploring all adjacent nodes using a queue.

Principle of BFS

The basic operating principle of BFS is as follows:

  1. Add the starting node to the queue and mark it as visited.
  2. Dequeue a node and explore all its adjacent nodes.
  3. Add any unvisited adjacent nodes to the queue and mark them as visited.
  4. Repeat steps 2 and 3 until the queue is empty.

The reason BFS guarantees the shortest path is that it processes all nodes at the same level.
By searching based on levels, the shortest path is ensured.

Problem-Solving Process

Now we will implement the algorithm necessary to solve the problem.
Below is a C++ code example for problem-solving. 


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int bfs(vector>& graph, int start, int end) {
    queue q;
    vector visited(graph.size(), false);
    vector distance(graph.size(), -1);
    
    q.push(start);
    visited[start] = true;
    distance[start] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
                
                if (neighbor == end) {
                    return distance[neighbor];
                }
            }
        }
    }
    return -1; // If there is no path 
}

int main() {
    int n, m;
    cin >> n >> m;
    vector> graph(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // undirected graph
    }

    int start, end;
    cin >> start >> end;

    int result = bfs(graph, start, end);
    cout << result << endl;

    return 0;
}

Code Explanation

The code above takes the number of nodes and edges as input,
constructs the graph based on the edge information, and then uses BFS to
find the shortest path between the starting and ending nodes.

  1. First, we include the necessary header files and declare using namespace std;.
  2. The bfs function takes the graph, starting node, and ending node as parameters.
  3. A queue is declared, and a vector visited to indicate visitation status is initialized.
  4. The starting node is added to the queue and marked as visited.
  5. The process continues while the queue is not empty, dequeuing nodes and exploring adjacent nodes.
  6. Unvisited adjacent nodes are added to the queue and their distance information is updated.
  7. When reaching the ending node, the corresponding distance is returned.
  8. The distance information is initialized to -1; when there is no path, it returns -1.

Results and Analysis

Compiling the above code and executing it with the sample input will print
the shortest path between the starting node and the ending node.
Since BFS explores all adjacent nodes, it guarantees the shortest path.
As the size of the graph increases, the search time increases proportionally, but
BFS is a suitable algorithm for most graph problems.

Complexity Analysis

The time complexity of BFS is O(V + E), where V is the number of nodes,
and E is the number of edges. The memory complexity is also O(V).
This complexity can vary depending on the structure of the graph.
In the worst case (e.g., complete graph), E can become V^2.

Conclusion

In this course, we solved the problem of finding the shortest path in a graph using C++
through the BFS algorithm. Understanding and implementing BFS is
an important aspect of coding tests, so be sure to practice thoroughly.
I hope you can build your skills through a wider variety of problems in the future.