学习了数据结构的图，但是算法并没有很熟练？也许我们需要一个总结！

一、图算法学习路线图

1. 图的遍历算法 (基础)

2. 拓扑排序 (有向图)

3. 最小生成树算法 (无向连通图)

4. 最短路径算法 (带权图)

5. 关键路径分析 (工程网络)

二、每个算法深度总结

1. 深度优先搜索 (DFS)

• 关键词：递归/栈、回溯、连通性、“一条路走到黑”
• 核心思想：从起点出发，沿着一条路径尽可能深入搜索，直到无法继续，然后回溯到上一个节点继续探索未访问的分支
• 记忆要点：像走迷宫，一条路走到死胡同再返回上一个岔路口
• 复杂度：O(V+E)，适合寻找路径、连通分量、环检测

2. 广度优先搜索 (BFS)

• 关键词：队列、层次遍历、“涟漪扩散”、最短路径(无权图)
• 核心思想：从起点出发，先访问所有直接相邻节点，再访问相邻节点的相邻节点，像水波一样一圈圈向外扩散
• 记忆要点：社交网络的"朋友的朋友"推荐机制
• 复杂度：O(V+E)，保证找到无权图的最短路径

3. 拓扑排序

• 关键词：DAG(有向无环图)、入度、依赖关系、线性序列
• 核心思想：对有向图的顶点进行排序，使得对于每条有向边(u,v)，u在排序中都出现在v之前
• 记忆要点：课程先修关系——先上基础课，再上专业课
• 关键步骤：反复选择入度为0的节点，删除其出边，更新邻居入度
• 复杂度：O(V+E)，只能应用于无环图

4. Prim算法 (最小生成树)

• 关键词：贪心、点集扩张、稠密图优化、局部最优
• 核心思想：从任意顶点开始，每次选择连接已选顶点集合和未选顶点集合的最小权边，逐步扩展生成树
• 记忆要点：像水滴从小到大凝结，每次吸附最近的水分子
• 复杂度：O(V²)，适合稠密图，与顶点数量关系更大

5. Kruskal算法 (最小生成树)

• 关键词：边排序、并查集、稀疏图优化、全局视角
• 核心思想：将所有边按权值排序，从小到大依次选择，如果加入该边不形成环，则将其加入生成树
• 记忆要点：像搭积木，从最小的开始，不形成圈圈
• 复杂度：O(ElogE)，适合稀疏图，与边的数量关系更大

6. Dijkstra算法 (单源最短路径)

• 关键词：贪心、优先队列、无负权、确定性
• 核心思想：每次从未确定最短路径的顶点中选择距离源点最近的，用它更新其他顶点的距离
• 记忆要点：“已知最近的点，它的邻居也该更新了”
• 关键限制：不能处理负权边
• 复杂度：O(V²)或O((V+E)logV)使用优先队列

7. Floyd算法 (全源最短路径)

• 关键词：动态规划、三重循环、全源、允许负权
• 核心思想：通过动态规划，考虑每个顶点k作为中间点，检查是否可以通过k使任意两点i,j间的路径更短
• 记忆要点：任意两点间，可能经过第三个点更短
• 关键公式：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
• 复杂度：O(V³)，简单但适用于小规模图

8. 关键路径 (AOE网络)

• 关键词：AOE网络、最早/最晚时间、工程调度、决定性路径
• 核心思想：在表示工程的有向图中，计算每个事件的最早/最晚发生时间，关键路径上的事件最早最晚时间相等
• 记忆要点：“木桶效应”——决定项目总时间的是最长路径
• 关键步骤：
  1. 拓扑排序计算最早发生时间
  2. 逆拓扑排序计算最晚发生时间
  3. 找出最早=最晚的节点序列
• 应用：工程项目管理、任务调度

三、终极记忆口诀

遍历算法两兄弟，DFS深搜回溯记，BFS广搜队列齐，
拓扑排序看入度，零入度先出不迟疑。

最小生成两算法，Prim点扩张适合密，Kruskal边排序查并集，
最短路径要分清，Dijkstra单源无负权，Floyd全源三循环递。

关键路径工程用，最早最晚时间须相等，
先拓扑后逆排序，项目工期它决定。

图论算法八样精，应用场景要分明，
关键词记心中存，算法思想自然清。

四、对比速记表