主要记录图的存储方式和两种遍历方式r (bfs和dfs)另外还有图中的各种例题

  • 存储方式:
    • 邻接表
    • 邻接矩阵
  • 遍历方式:
    • bfs : 广度优先遍历,比如二叉树的层次遍历
    • dfs: 深度优先遍历,也就是回溯算法

例题

  1. 所有可达路径 深度优先遍历即可,注意深度优先遍历的过程就是回溯的过程,需要遍历所有与当前元素连接的元素,之后就者这一个元素不断递归找到最终需要的元素即可 另外注意图的存储方法有邻接表和邻接矩阵的方式: dfs_邻接表.cpp dfs_邻接矩阵.cpp
  2. 岛屿的数量 这里只需要定义方向,之后根据方向来进行深度优先遍历和广度优先遍历即可 岛屿的数量_dfs.cpp 岛屿的数量_bfs.cpp
  3. 岛屿的最大面积 和上面一样 岛屿的最大面积_dfs.cpp 岛屿的最大面积_bfs.cpp
  4. 孤岛的最大面积 和上面一样,可以首先遍历靠近陆地的所有岛屿
  5. 沉没孤岛 还是和上面一样的写法
  6. 水流问题 注意到遍历方法 dfs 和 bfs 的作用就是遍历,可以用于标记可以到达的地方,所以此时只需要从边界标记边界可以访问的每一个节点即可,对于边界上的节点使用dfs和 bfs 即可 水流问题.cpp
  7. 建造最大岛屿 可以首先把各个陆地使用序号进行标记,标记完成之后就可以找到所有的有水的地方,找到有水的地方之后就可以向两边进行遍历,一旦遍历到标记的地方就可以累加了,之后针对于累加值选取其中的最大值即可 建造最大岛屿.cpp
  8. 字符串接龙 类似于层序遍历,注意把每一层遍历完成之后才把层数进行累加即可 字符串接龙.cpp
  9. 有向图的完全可达性 可以利用深度优先遍历或者广度优先遍历,类似于无向图 有向图的完全可达性.cpp
  10. 岛屿的周长 本质上就是两种遍历方法加上一定的条件,所以这里只需要改变遍历的条件即可
  • 如下是并查集中的问题(注意并查集的主要作用就是判断两个元素是否存在于同一个集合中):
  1. 寻找存在的路径 判断终点和起始点在同一个集合中即可,并查集模板题目 寻找存在的路径.cpp
  2. 冗余连接II 首先题目中的含义就是每一个节点的入度都是 0或者1,同时由于只有n条边,所以之可能出现有一个入度为2的节点或者入度全部都是 1的节点,分别讨论两种情况即可,注意这里并查集的作用只是用于判断是否存在环路,也就是是否可以构成有向树 冗余连接II.cpp
  3. prim算法 注意 prim算法的过程,在这一个过程中需要维护一个minDist 数组以及一个最小生成树木(如果需要记录可以使用 vector，如果指需要指示是否加入到树中只需要使用 一个bool类型的数组) (注意利用循环开控制获取的边的数量):
    • 首先在 minDist数字中找到距离当前最小生成树距离最间的节点
    • 节点加入到树中
    • 更新 minDist 数组 prim.cpp
  4. kruskal算法 还是一样拥有计算最短路径,步骤为:
    • 把边按照权值大小排列
    • 遍历集合,集合中不构成环的边相连即可(使用并查集) kruskal.cpp
  • prim算法和 kruskal算法要解决的问题都是求解把所有节点串联起来的边的最短总长度,如果节点多,边少的情况可以优先使用 kruskal算法,对于节点稀疏的情况可以使用 prim算法
  1. 拓扑排序 解决节点之后的依赖型问题,解决思路也就是加上了一定逻辑的 bfs , 把入度为 0节点看成根节点,之后不断删除子结点的入度知道入度为 0 就可以加入到结果集中了,解题步骤:
    • 首先记录每一个节点的入度
    • 把入度为 0 的节点入队列
    • 把队列中的元素出队列加入到结果集中并且把这一个节点关联的节点的入度减少 -- ,如果这些节点的入度减少为 0 ,按么就可以加入到队列中即可 tupu.cpp
  • 注意拓扑排序解决节点之间的依赖关系,笔记课程关系或者软件关系之间的依赖关系(比如 Linux的软件依赖管理)
  1. dijkstra算法 主要用于解决最短路径问题,和prim算法类似都需要使用到 minDist数组,只不过 prim算法中的minDist数组的作用是记录每一个节点到达最小生成树的距离,dijkstra算法中是记录者每一个节点到达源点的距离,dijkstra算法的步骤为:
    • 首先找到距离源点最近的节点(外层需要遍历所有的节点所以需要遍历 1 - n)
    • 把最近的节点变为访问过的状态
    • 更新所有节点到开始点的距离即可 dijkstra_1.cpp
      同时注意到第一部中每一次都要遍历找到距离源点最近的节点,所以这里可以使用最小堆来初始化边,每一次都从最小堆中取出边来即可 dijkstra_heap.cpp 但是注意 dijkstra算法的特点就是边的权值不可以为负数,这是由于对于已经访问过的节点不可以重复访问,但是回路中出现负值的时候就会导致可能被访问过的节点还需要被重复访问才可以
  2. Bellman_ford算法 也是求解单源最短路径问题,但是允许有负值权值,重点就是一个松弛操作,一次松弛操作也就是对于一个边,查看起点边到源点的距离是否更新,如果更新就需要更新这一条边了,本质上就是动态规划的一种思想,由于一次松弛其实就是求解和源点一条边相连的边的最短距离(最少) , 如果需要更新所有的边就需要松弛 N - 1 次即可 Bellman_ford.cpp 感觉类似于层序遍历,也就是每一层每一层的松弛
  3. SPFA算法 Bellman_ford算法的队列优化形式,注意在 Bellman_ford算法中很多更新都是没有用处的,也就是 虽然每一次更新周围一层的数据,但是还是会更新许多没有用的位置,所以可以进行顺序更新,也就是遍历到那里就可以更新到哪里,由于上面说过类似于层序遍历,所以可以使用队列进行优化,也就是把松弛过后的节点加入到队列中,这些节点后面的节点才值得更新 SPFA算法.cpp
  4. Bellman_ford算法判断负权回路 负权回路(也就是一个通路中所有边的权值为负), 注意到 Bellman_ford算法其实就是一个不断松弛的过程,所以在松弛的过程中如果松弛到 N次还是回到是最短路径减少那么就说明此时存在负权回路,对于spfa算法,如果一个节点入队N次并且权值减少那么也说明形成了负权回路
  5. Bellman_ford算法判断单源最短路径 Bellman_ford算法的本质就是bfs之前由于只需要把每一条边松弛N次即可,所以没有体现广度优先搜索的特点,这里要求中间只可以经过K个城市这一个限定就使得广度优先遍历只需要遍历K层即可,并且注意每一次使用的minDist都需要是上一层更新的minDist防止互相依赖关系,并且使用spfa的时候就像树的层序遍历一样记录队列中的节点依次出队即可(可以利用一个visited数组防止重复入队)
  • 注意dijkstra算法和Bellman_ford算法都是用于解决单元最短路径问题的,两种算法都需要minDist数组,dijkstra算法类似于prim算法,只是对于minDist的定义和更新方式不同,Bellman_ford注意对于边的一个松弛操作,同时也需要掌握dijkstra 的优先队列优化方法和SPFA算法, 由于都是求解最短路径所有基本思想都是bfs
  1. floyd算法 floyd算法要解决的问题就是多源最短路径长度,本质上还是动态规划,这里dp数组的含义就是: dp[i][j][k] 表示从 i -> j 以 k 为中间节点的最短距离,递推公式为: dp[i][j][k] = min(dp[i][j][k - 1] , dp[i][k][k - 1] + dp[k][j][k - 1]) 有递推公式,可以看出需要从三维平面的下面向上面遍历,同时也可以使用二维数组来模拟这一个过程,就像背包问题中一样(注意回忆01背包和完全背包问题的解法) floyd.cpp
  2. Astar算法 A*算法的核心算法就是bfs,只不过是根据每一条边的一个权值进行排序操作,权值小的就可以放在前面首先取出,这一个过程可以使用一个小根堆来代替队列即可 Astar.cpp