DFS/BFS遍历图(一)
DFS遍历图:深度优先搜索,基于递归回溯的方式来遍历图
BFS遍历图:宽度优先搜索,基于队列线性化的方式来遍历图
时间复杂度一般O(n+m)
1.AcWing 2060.奶牛选美
法一:DFS找连通块+暴力枚举两个连通块坐标求最短路
思路:
1.深搜将两个连通块的坐标存在两个向量中
2.通过暴力枚举两个连通块的坐标求最短距离
法二:BFS找连通块+暴力枚举两个连通块坐标求最短路
思路:
1.宽搜将两个连通块的坐标存在两个向量中
2.通过暴力枚举两个连通块的坐标求最短距离
法三:两个不同阶段的BFS衔接
思路:
1.先宽搜遍历第一个连通块
2.在第一个连通块基础上往外一步一步扩展,得到到达第二个连通块的最短路再减去1就是需要涂的数量
实现:
1.需要两个队列q1,q2
2.q1用于第一个连通块的宽搜,顺带将第一个连通块外一层的点放入q2队列作为第二次宽搜的起点(重点)
3.q2以第一个连通块外面一层的点为起始,一步一步往外宽搜找到达第二个连通块的最短路即可
总结:
1.法一,法二本质一样,但时间复杂度最坏O(n^2*m^2)
2.法三时间复杂度为O(nm)
2.AcWing 846.树的重心
法一:dfs遍历图
思路:
1.深搜遍历每一个数:dfs(i)时,i作为割点求mi=max(b1,b2...,bi,...)(bi为割掉i点后其他连通块的结点数量)
2.答案ans=min(m1,m2...,mi,...)
实现:
1.链式前向星存无向图
2.st数组存状态,表示已经遍历过的点
3.dfs(i)返回i结点以及其所有子树结点个数之和
4.为求得完整的m,注意外加m=max(m,n-子树结点个数和-1)统计父结点所在连通块结点数量
总结:
1.图的dfs遍历,时间复杂度O(n+m)
3.AcWing 1207. 大臣的旅费
法一:dfs遍历图
思路:
1.两次dfs遍历图,找树的直径(最长距离)即可
实现:
1.链式前向星存无向图
2.st数组存状态,表示已经遍历过的点,dist数组存距离
3.先从任意一点s开始dfs遍历,找到距离s最远的t
4.再从t开始dfs遍历,找到的最远距离即为树的直径
总结:
1.图的dfs遍历,时间复杂度O(n+m)
4.AcWing 1112. 迷宫
法一:dfs遍历图
思路:
1.起点开始dfs遍历图,找目标
法二:bfs遍历图
思路:
1.起点开始bfs遍历图,找目标
2.注意bfs需要特判:起点和终点是否 重合无障碍物或其中一个有障碍物
总结:
1.图的dfs遍历和bfs遍历——时间复杂度最坏O(nm)