广度优先搜索

广度优先搜索

广度优先搜索（BFS）是一种图搜索的算法。在图中，BFS搜索算法是从根节点开始，沿着树的宽度遍历图的节点。BFS算法通常用队列来实现。

算法原理

BFS算法的原理是从根节点开始，将子节点逐层放入队列中，然后依次将队列中的节点取出，并将其未访问过的相邻节点加入队列中，直到队列为空。如果所有节点都被访问过，则搜索完毕。

下面是BFS算法的伪代码：

BFS(G, s)
    for each vertex v in G
        color[v] = white
        d[v] = infinity
        p[v] = null
    color[s] = gray
    d[s] = 0
    p[s] = null
    enqueue(Q, s)
    while Q is not empty
        u = dequeue(Q)
        for each v in adj[u]
            if color[v] = white
                color[v] = gray
                d[v] = d[u] + 1
                p[v] = u
                enqueue(Q, v)
        color[u] = black
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在上面的伪代码中，G表示图，s是起始节点，color[v]表示节点v的颜色，d[v]表示节点v的距离，p[v]表示节点v的前驱节点，Q表示一个队列。

在执行BFS算法时，所有节点的颜色初始化为白色，距离初始化为正无穷大，前驱节点初始化为空。起始节点的颜色为灰色，距离为0，前驱节点为空，将其加入队列中。当队列不为空时，从队列中取出第一个节点，将其未访问过的相邻节点加入队列中，并将颜色设为灰色，距离设置为父节点距离+1，前驱节点设置为父节点。将颜色设置为黑色，表示已访问过。

算法实现

下面是BFS算法的Python实现：

from collections import deque

def bfs(graph, start):
    # 将所有节点初始化为未访问
    visited = {node: False for node in graph}

    # 创建一个队列，并将起始节点加入队列中
    queue = deque()
    queue.append(start)
    visited[start] = True

    # 开始BFS算法
    while queue:
        node = queue.popleft()
        print(node)

        # 将所有未访问过的相邻节点加入队列中
        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 测试代码
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

在上面的代码中，我们首先将所有节点初始化为未访问（visited），然后创建一个队列（queue），将起始节点添加到队列中，并将起始节点的visited标记为True。

然后开始BFS算法，当队列不为空时，取出队列中的第一个节点，并将其打印出来。然后将其所有未访问过的相邻节点加入队列中，并将visited标记为True。

在上面的代码中，我们使用了Python的deque类来实现队列，这是一个双向队列，可以在队列的头部和尾部快速添加和删除元素。

算法应用

BFS算法的应用非常广泛，比如最短路径问题、连通性问题、拓扑排序等等。

下面给出两个例子：

例子1：最短路径问题

最短路径问题是指在无向图或有向图中找到从起点到目标节点的最短路径。BFS算法可以很方便地解决这个问题，因为BFS算法的特点是先访问距离起始节点最近的节点，因此可以保证找到的路径是最短的。

from collections import deque

def bfs_shortest_path(graph, start, end):
    # 将所有节点初始化为未访问
    visited = {node: False for node in graph}

    # 创建一个队列，并将起始节点加入队列中
    queue = deque()
    queue.append(start)
    visited[start] = True

    # 用来记录每个节点的前驱节点
    path = {start: None}

    # 开始BFS算法
    while queue:
        node = queue.popleft()

        # 如果到达目标节点，返回路径
        if node == end:
            shortest_path = []
            while end != start:
                shortest_path.append(end)
                end = path[end]
            shortest_path.append(start)
            shortest_path.reverse()
            return shortest_path

        # 将所有未访问过的相邻节点加入队列中
        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
                path[neighbor] = node

# 测试代码
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs_shortest_path(graph, 'A', 'F'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

在上面的代码中，我们在BFS算法中加入了一个path字典来记录每个节点的前驱节点。当到达目标节点时，我们可以从终点开始往前遍历path字典，直到到达起始节点，这样就得到了一条最短路径。

例子2：连通性问题

连通性问题是指在无向图或有向图中判断两个节点之间是否存在路径。BFS算法也可以很方便地解决这个问题，如果从起始节点能够到达目标节点，则说明两个节点之间存在路径。

from collections import deque

def bfs_is_reachable(graph, start, end):
    # 将所有节点初始化为未访问
    visited = {node: False for node in graph}

    # 创建一个队列，并将起始节点加入队列中
    queue = deque()
    queue.append(start)
    visited[start] = True

    # 开始BFS算法
    while queue:
        node = queue.popleft()

        # 如果到达目标节点，返回True
        if node == end:
            return True

        # 将所有未访问过的相邻节点加入队列中
        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

    # 没有找到目标节点，返回False
    return False

# 测试代码
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': ['E'],
    'E': ['F'],
    'F': []
}

print(bfs_is_reachable(graph, 'A', 'F'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

在上面的代码中，我们在BFS算法中判断是否到达目标节点，如果到达则返回True，否则返回False。

总结

BFS算法是一种简单而又实用的图搜索算法，其原理是从根节点开始，逐层遍历图的节点，并使用队列来实现。BFS算法具有广泛的应用，比如最短路径问题、连通性问题、拓扑排序等等。