四川住房建设和城乡建设厅假网站,网站手机端跳转页面模板,qt开发安卓app,社交类电商平台理论基础
理论基础部分依然沿用代码随想录教程中的介绍#xff1a;
图的种类 度 连通性
连通性用于表示图中节点的连通情况。 如果有节点不能到达其他节点#xff0c;则为非连通图#xff0c;想象将多个水分子表示为图#xff0c;不考虑非键作用#xff0c;这张图就不是…理论基础
理论基础部分依然沿用代码随想录教程中的介绍
图的种类 度 连通性
连通性用于表示图中节点的连通情况。 如果有节点不能到达其他节点则为非连通图想象将多个水分子表示为图不考虑非键作用这张图就不是连通图。 强连通图的概念只针对有向图因为有向图边的方向也会影响各个节点之间的连通性。 无向图中 节点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表示终点我们遍历的时候用来判断当 xn 时候 标明找到了终点。
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, x1, nn, path[1], resultresult)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)
