03.图的广度优先搜索知识

图的广度优先搜索知识 #

1. 广度优先搜索简介 #

广度优先搜索算法(Breadth First Search):简称为 BFS,又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始,沿着树的宽度遍历树或图的节点。如果所有节点均被访问,则算法中止。

广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问,后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点,所以广度优先搜索可以通过「队列」来实现。

2. 广度优先搜索过程演示 #

接下来我们以一个无向图为例,演示一下广度优先搜索的过程。

我们用邻接字典的方式存储无向图结构,对应结构代码如下:

1
2
3
4
5
6
7
8
9
# 定义无向图结构
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

该无向图对应的邻接字典表示:无向图中有 ABCDEF6 个节点,其中与 A 节点相连的有 BC 两个节点,与 B 节点相连的有 ACD 三个节点,等等。

该无向图的结构如图左所示,其宽度优先搜索的遍历路径如图右所示。

其广度优先搜索的遍历过程如下动图所示。

3. 基于队列实现的广度优先搜索 #

3.1 基于队列实现的广度优先搜索实现步骤 #

  1. 定义 graph 为存储无向图的字典变量,start 为开始节点,def bfs(graph, start): 为队列实现的广度优先搜索方法。
  2. 定义 visited 为标记访问节点的 set 集合变量,queue 为存放节点的队列。
  3. 首先将起始节点标记为访问,即 visited.add(start)。并将其放入队列 queue中,即 queue.append(start)
  4. 从队列中取出第一个节点 node_u。访问节点 node_u,并对节点进行相关操作(看具体题目要求)。
  5. 遍历与节点 node_u 相连并构成边的节点 node_v
    • 如果 node_v 没有被访问过(即 node_v 不在 visited 中):则将 node_v 节点放入队列中,并标记访问,即 q.append(node_v)visited.add(node_v)
  6. 重复步骤 4 ~ 5,直到队列 queue 为空。

3.2 基于队列实现的广度优先搜索实现代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import collections

def bfs(graph, start):
    visited = set()
    queue = collections.deque([])
    
    visited.add(start)
    queue.append(start)
    
    while queue:
        node_u = queue.popleft()
        print(node_u)
        for node_v in graph[node_u]:
            if node_v not in visited:
                visited.add(node_v)
                queue.append(node_v)

4. 广度优先搜索应用 #

4.1 克隆图 #

4.1.1 题目链接 #

4.1.2 题目大意 #

描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 adjList[i] 表示值为 i + 1的节点的邻接列表,adjList[i][j] 表示值为 i + 1 的节点与值为 adjList[i][j] 的节点有一条边。

要求:返回该图的深拷贝。

说明

  • 节点数不超过 100
  • 每个节点值 $Node.val$ 都是唯一的,$1 \le Node.val \le 100$。
  • 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  • 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  • 图是连通图,你可以从给定节点访问到所有节点。

示例

1
2
3
4
5
6
7
8
输入adjList = [[2,4],[1,3],[2,4],[1,3]]
输出[[2,4],[1,3],[2,4],[1,3]]
解释
图中有 4 个节点
节点 1 的值是 1它有两个邻居节点 24 
节点 2 的值是 2它有两个邻居节点 13 
节点 3 的值是 3它有两个邻居节点 24 
节点 4 的值是 4它有两个邻居节点 13 

1
2
输入adjList = [[2],[1]]
输出[[2],[1]]

4.1.3 解题思路 #

思路 1:广度优先搜索 #
  1. 使用哈希表 visited 来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。使用队列queue 存放节点。
  2. 根据起始节点,创建一个新的节点,并将其添加到哈希表 visited 中,即 visited[node] = Node(node.val, [])。然后将起始节点放入队列 queue中,即 queue.append(node)
  3. 从队列中取出第一个节点 node_u。访问节点 node_u
  4. 遍历与节点 node_u 相连并构成边的节点 node_v
    1. 如果 node_v 没有被访问过(即 node_v 不在 visited 中):
      1. 则根据 node_v 创建一个新的节点,并将其添加到哈希表 visited 中,即 visited[node_v] = Node(node_v.val, [])
      2. 然后将 node_v 节点放入队列 queue 中,即 queue.append(node_v)
  5. 重复步骤 3 ~ 4,直到队列 queue 为空。
  6. 广度优先搜索结束,返回起始节点的克隆节点(即 visited[node])。
思路 1:代码 #
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        
        visited = dict()
        queue = collections.deque()

        visited[node] = Node(node.val, [])
        queue.append(node)

        while queue:
            node_u = queue.popleft()
            for node_v in node_u.neighbors:
                if node_v not in visited:
                    visited[node_v] = Node(node_v.val, [])
                    queue.append(node_v)
                visited[node_u].neighbors.append(visited[node_v])
        
        return visited[node]
思路 1:复杂度分析 #
  • 时间复杂度:$O(n)$。其中 $n$ 为图中节点数量。
  • 空间复杂度:$O(n)$。

4.2 岛屿的最大面积 #

4.2.1 题目链接 #

4.2.2 题目大意 #

描述:给定一个只包含 01 元素的二维数组,1 代表岛屿,0 代表水。一座岛的面积就是上下左右相邻的 1 所组成的连通块的数目。

要求:计算出最大的岛屿面积。

说明

  • $m == grid.length$。
  • $n == grid[i].length$。
  • $1 \le m, n \le 50$。
  • $grid[i][j]$ 为 01

示例

1
2
3
4
5
6
7
输入grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出6
解释答案不应该是 11 因为岛屿只能包含水平或垂直这四个方向上的 1 


输入grid = [[0,0,0,0,0,0,0,0]]
输出0

4.2.3 解题思路 #

思路 1:广度优先搜索 #
  1. 使用 ans 记录最大岛屿面积。
  2. 遍历二维数组的每一个元素,对于每个值为 1 的元素:
    1. 将该元素置为 0。并使用队列 q 存储该节点位置。使用 temp_ans 记录当前岛屿面积。
    2. 然后从队列 q 中取出第一个节点位置 (i, j)。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为 0(避免重复搜索)。并将其加入到队列中。并累加当前岛屿面积,即 temp_ans += 1
    3. 不断重复上一步骤,直到队列 q 为空。
    4. 更新当前最大岛屿面积,即 ans = max(ans, temp_ans)
思路 1:代码 #
 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
import collections

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        rows, cols = len(grid), len(grid[0])
        ans = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    temp_ans = 1
                    q = collections.deque([(i, j)])
                    while q:
                        i, j = q.popleft()
                        for direct in directs:
                            new_i = i + direct[0]
                            new_j = j + direct[1]
                            if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols or grid[new_i][new_j] == 0:
                                continue
                            grid[new_i][new_j] = 0
                            q.append((new_i, new_j))
                            temp_ans += 1

                    ans = max(ans, temp_ans)
        return ans
思路 1:复杂度分析 #
  • 时间复杂度:$O(n \times m)$,其中 $m$ 和 $n$ 分别为行数和列数。
  • 空间复杂度:$O(n \times m)$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者