深度优先搜索(BFS) 是一种用于搜索图或树数据结构中的节点的方法。这里，我们考虑一个具有 $n$ 个端点的无向图，编号范围为 [0, n)。每个节点最多拥有 4 条出边。边集 edges 定义为 {{n1, n2}, {n3, n4}, ...} 表示 n1 和 n2 之间，n3 和 n4 之间等存在边连接。给定起始节点 s 和目标节点 d，我们的任务是找出从 s 到 d 的最少边数。如果无法到达目标节点，返回 -1。此图中可能存在环，但不存在自环、重边，且图不一定是连通的。

实现思路

  1. 使用广度优先搜索 (BFS) 进行图遍历，依次访问图的每一层，确保找到最短路径。
  2. 创建一个队列记录待访问节点，维护一个数组记录每个节点的最短距离。
  3. 在遍历过程中，记录访问过的节点，避免重复搜索。
  4. 遍历所有出边，判断是否到达目标节点 d。

C++ 实现代码

#include 
#include 
#include 
#include 

int minEdgeBFS(int n, std::vector>& edges, int s, int d) {
    std::vector> graph(n);
    for (auto edge : edges) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }

    std::vector distance(n, -1);
    std::queue q;
    distance[s] = 0;
    q.push(s);

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

        for (int neighbor : graph[node]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
                if (neighbor == d) return distance[neighbor];
            }
        }
    }
    return -1;
}

关键代码说明

  • Graph 构建：使用 graph 数组存储邻接列表。
  • 初始化： distance 数组记录每个节点到起始节点的最短路径长度。
  • BFS遍历：节点出队后，检查每一个相邻节点。如果目标节点被访问，返回当前路径长度。

测试样例

int main() {
    int n = 5;
    std::vector> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
    int s = 0, d = 4;
    std::cout << "Minimum edges from " << s>

输出：

Minimum edges from 0 to 4 is: 4

此实现的复杂度为 $O(n+e)$，适用于密集和稀疏图。