代码随想录D50-51 图论 Python

理论基础

理论基础部分依然沿用代码随想录教程中的介绍：

图的种类

度

连通性

连通性用于表示图中节点的连通情况。

如果有节点不能到达其他节点，则为非连通图，想象将多个水分子表示为图，不考虑非键作用，这张图就不是连通图。

强连通图的概念只针对有向图，因为有向图边的方向也会影响各个节点之间的连通性。

无向图中 节点3 、节点4 构成的子图不是该无向图的联通分量。因为必须是极大联通子图才能是连通分量，所以 必须是节点3、节点4、节点6 构成的子图才是连通分量。 

 图的构造

- 邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

邻接矩阵的优点：

• 表达方式简单，易于理解

• 检查任意两个顶点间是否存在边的操作非常快

• 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

• 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

- 邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

邻接表的优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高

• 遍历节点连接情况相对容易

缺点：

• 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。

• 实现相对复杂，不易理解

图的遍历方式

图的遍历方式基本是两大类：

• 深度优先搜索（dfs）

• 广度优先搜索（bfs）

在讲解二叉树章节的时候，其实就已经讲过这两种遍历方式。

二叉树的递归遍历，是dfs 在二叉树上的遍历方式。

二叉树的层序遍历，是bfs 在二叉树上的遍历方式。

深度优先搜索理论基础 重要！

对比bfs（广度优先搜索来说）：

• dfs是指定一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯），回到上一个节点，然后继续。

• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

因此我们可以发现，深搜和广搜在图结构上是有一个范式框架的，首先学习深搜框架：

深度优先搜索的本质是回溯算法，回溯就涉及到递归。因此可以使用递归框架：

1. 确认递归函数，确认传入参数

2. 确认函数终止条件

3. 图中涉及到节点出发路径，因此要额外加上路径

98. 所有可达路径

要点：

找到从1到n的所有路径，图遍历方法的考察。输入第一行为节点数和边数量，之后为边索引。

解法：

1. 确认递归函数，参数

首先我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。

还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候 标明找到了终点。

2. 确认终止条件

当目前遍历的节点 为 最后一个节点 n 的时候 就找到了 一条 从出发点到终止点的路径。

3. 处理目前搜索节点出发的路径

接下来是走，当前遍历节点x的下一个节点。这个步骤的逻辑如下：

首先 是要找到 x节点指向了哪些节点。

然后 选中的x所指向的节点，加入到单一路径来。

最后 进入下一层递归

实现：

def dfs(graph, x, n, path, result):if x == n:## 一定要注意使用copy 保证过程中所有路径的记录result.append(path.copy())returnfor i in range(1, n + 1):if graph[x][i] == 1:# 判断边之后将节点路径加入path.append(i)# 递归继续深度搜索dfs(graph, i, n, path, result)# 退出dfs说明当前路径结束 回溯path.pop()def main():n, m = map(int, input().split())## 方便直接对应节点graph = [[0] * (n + 1) for _ in range(n + 1)]for i in range(m):s, t = map(int, input().split())graph[s][t] = 1 result = []## 启动深度优先搜索dfs(graph, x=1, n=n, path=[1], result=result)if not result:print(-1)else:## 注意输出格式for path in result:print((' ').join(map(str, path)))if __name__ == "__main__":main()

广度优先搜索理论基础 重要！

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

BFS是一圈一圈的搜索过程，我们用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。

搜索的直观过程如下：

在广度优先搜索中，即使有障碍，搜索也是能够继续执行的。 

99. 岛屿数量 广度优先

要点：

遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。

在广度搜索函数中，我们需要指定一个优先队列deque，以保证搜索可以逐层进行。

同时，考虑搜索的剪枝，我们需要在搜索过程中严谨地维护已访问节点，以及判断可以遍历的合法节点。

实现：

from collections import dequedirections = [[0, 1], [1, 0], [-1, 0], [0, -1]]def bfs(graph, visit, x, y):## 初始化一个队列 执行先进先出que = deque([])## 将当前传入节点加入队列que.append([x, y])## 只要计算了节点 就先记录visit防止重复visit[x][y] = Truewhile que:cur_x, cur_y = que.popleft()## 遍历四个方向上的所有节点 每个节点遍历完就加入队列 等待下一层for i, j in directions:next_x, next_y = cur_x + i, cur_y + j## 排除不合法节点if next_y < 0 or next_x < 0 or next_x >= len(graph) or next_y >= len(graph[0]):continue## 将之前没有访问的节点进行记录 标记visit if not visit[next_x][next_y] and graph[next_x][next_y] == 1:visit[next_x][next_y] = True## 同时将该节点加入队列 进入下一层遍历que.append([next_x, next_y])def main():n, m = map(int, input().split())graph = []## 初始化节点分布for i in range(n):graph.append(list(map(int, input().split())))visit = [[False] * m for _ in range(n)]res = 0## 逐个节点遍历 每次执行广度优先 直到队列元素周围没有岛屿for i in range(n):for j in range(m):if graph[i][j] == 1 and not visit[i][j]:res += 1bfs(graph, visit, i, j)print(res)if __name__ == '__main__':main()

 99. 岛屿数量 深度优先

要点：

对于节点的访问而不是路径的访问，深搜的关联条件会多一些：

1. 确认递归函数，参数

递归函数对节点的四个方向进行遍历，如果存在符合要求的节点，就一直遍历直到一次深搜终止。此时无需pop，因为不用记录路径。回到四个方向的循环中会自动开始下一个方向的遍历，以此找完全部数值为1的节点。

2. 确认终止条件

当前节点的值为0，或者已经被遍历过，则终止并回退。

3. 处理目前搜索节点出发的路径

在外层首先做一个对所有节点的遍历，保证代入递归的节点符合岛屿+未访问的要求。一旦进入递归，就意味着我们来到了一个新的岛屿。

实现：

directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]def dfs(graph, visit, x, y):## 没有岛屿或下一个节点已经被访问if graph[x][y] == 0 or visit[x][y]:return## 记录当前访问的节点visit[x][y] = True## 根据方向访问下一个节点for i, j in directions:next_x, next_y = x + i, y + j # 排除不合法节点if next_x < 0 or next_x >= len(graph) or next_y < 0 or next_y >= len(graph[0]):continue## 执行深度优先搜索dfs(graph, visit, next_x, next_y)def main():n, m = map(int, input().split())graph = []## 初始化节点分布for i in range(n):graph.append(list(map(int, input().split())))res = 0visit = [[False] * m for _ in range(n)]for i in range(n):for j in range(m):## 深搜递归退出回到循环时意味着上一个岛屿一定被遍历完了if graph[i][j] == 1 and not visit[i][j]:res += 1 dfs(graph, visit, i, j)print(res)

99. 岛屿的最大面积 深度优先

 

要点：

本题需要比对不同岛屿之间的最大面积，言外之意就是要记录遍历过的岛屿，使用深度优先搜索时可以在dfs内部计数，更简便的技巧是定义全局变量，无参实现主函数和dfs的传递。

实现：

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]def dfs(graph, visit, x, y):global resultif graph[x][y] == 0 or visit[x][y]:returnvisit[x][y] = True  # 先标记为访问过result += 1  # 计数for i, j in directions:next_x, next_y = x + i, y + j if next_x < 0 or next_x >= len(graph) or next_y < 0 or next_y >= len(graph[0]):continuedfs(graph, visit, next_x, next_y)  # 使用next_x和next_y进行递归调用def main():global resultn, m = map(int, input().split())graph = []for i in range(n):graph.append(list(map(int, input().split())))max_res = 0visit = [[False] * m for _ in range(n)]for i in range(n):for j in range(m):if graph[i][j] == 1 and not visit[i][j]:result = 0  # 初始化为0dfs(graph, visit, i, j)max_res = max(max_res, result)print(max_res)if __name__ == "__main__":main()

 99. 岛屿的最大面积 广度优先

要点：

广度优先搜索仍然遵循层级关系，使用deque记录层次；在每次遍历到新的节点时记录即可。

实现：

from collections import dequedirections = [[0, 1], [1, 0], [0, -1], [-1, 0]]def bfs(graph, visit, x, y):result = 1que = deque([])que.append([x, y])visit[x][y] = Truewhile que:cur_x, cur_y = que.popleft()for i, j in directions:next_x, next_y = cur_x + i, cur_y + j if next_x < 0 or next_x >= len(graph) or next_y < 0 or next_y >= len(graph[0]):continueif not visit[next_x][next_y] and graph[next_x][next_y] == 1:visit[next_x][next_y] = Trueque.append([next_x, next_y])result += 1return resultdef main():n, m = map(int, input().split())graph = []for i in range(n):graph.append(list(map(int, input().split())))max_res = 0visit = [[False] * m for _ in range(n)]for i in range(n):for j in range(m):if graph[i][j] == 1 and not visit[i][j]:result = bfs(graph, visit, i, j)max_res = max(max_res, result)print(max_res)