BFS

2025-04-22

Algorithm

无标签

文章目录

概述#

What Is#

BFS 全称是 Breadth First Search，也就是广度优先搜索。

所谓广度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

结果#

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的 。

本质#

在实现 BFS 的时候，本质上我们把未被访问过的节点放在一个称为 open 的容器中，而把已经访问过了的节点放在一个称为 closed 容器中。

链式前向星实现#

实现代码#

链式前向星的实现见图的存储。

伪代码

1
bfs(s){
2
    q = new queue()
3
    q.push(s);
4
    visited[s] = true;
5
    while(!q.empty())
6
    {
7
        u = q.pop();
8
        for each edge(u, v)
9
        {
10
            if (!visited[v])
11
            {
12
                q.push(v);
13
                visited[v] = true;
14
            }
15
        }
16
    }
17
}

C++

1
struct Edge {
2
    int to;
3
    int next;
4
    int w;
5
};
6
// u代表起始的顶点
7
void bfs(int u) {
8
    queue<int> q;
9
    q.push(u);
10
    visited[u] = true;
11
    // 额外信息
12
    d[u] = 0;
13
    p[u] = -1;
14

15
    while (!q.empty())
16
    {
17
        u = q.front();
18
        q.pop();
19
        for (Edge e = head[u]; e.next != -1; e = edge[e.next].next)
20
        {
21
            if (!visited[e.to]) {
22
                q.push(e.to);
23
                visited[e.to] = true;
24

25
                d[e.to] = d[u] + 1;
26
                p[e.to] = u;
27
            }
28
        }
29
    }
30
}