数据结构与算法--图的应用

回顾

图的遍历方法：

• 深度优先遍历 (DFS)：从任意顶点开始，访问其未访问过的邻接点，直至全部访问完毕。
• 广度优先遍历 (BFS)：从任意顶点开始，访问其所有未访问过的邻接点，然后是下一层的邻接点，直至所有顶点被访问。

提要

• 最小生成树的概念。
• 最小生成树的构造算法：
  • 普里姆 (Prim) 算法
  • 克鲁斯卡尔 (Kruskal) 算法
• 单源点最短路径。
• 拓扑排序。

连通图

连通图：图中任意两个顶点都是连通的。在连通图中，从任意顶点出发进行深度优先遍历或广度优先遍历，都可以访问图中所有其他顶点。

生成树

生成树：包含连通图全部顶点的极小连通子图，即以最少的边连接连通图中所有的顶点。

最小生成树

最小生成树：带权连通图的所有生成树中权值之和最小的生成树。在实际问题中，如管道铺设问题，可以应用最小生成树来最小化成本。
最小生成树：带权连通图的所有生成树中权值之和最小的生成树。
在实际问题中的应用：管道的铺设问题。
n 个小区只需铺设 n-1 条管线就能连通，各条管线的投资成本不同，如何使得总的投资成本最低？最小生成树。

构造最小生成树的算法

• 普里姆 (Prim) 算法：从任一顶点开始，逐步扩展最小生成树，每次添加权值最小的边。
• 克鲁斯卡尔 (Kruskal) 算法：按边权值从小到大的顺序选择边，形成最小生成树，不形成环。

普里姆(Prim)算法

示例：
求解过程：

• 初始化U={v}。v到其他顶点的所有边为候选边；
• 重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：
  • 从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
  • 考察当前V-U中的所有顶点j，修改候选边：若 (k, j) 的权值小于原来和顶点 j 关联的候选边，则用 (k, j) 取代后者作为候选边。

克鲁斯卡尔(Kruskal)算法

假设N=(V,E)是连通网(带权的图)，令最小生成树的初始状态为包含全部n个顶点，但没有边的非连通图T=(V,{ })，图中每个顶点自成一个连通分量。
在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条权值最小的边。依此类推，直至所有顶点都在同一连通分量上为止。

示例：

求解过程：

• T的初始状态：包含n个顶点、不包含边的森林：T=(V，Ø )；
• 按权值递增的顺序选择E中的n-1条安全边(u，v)，并加入T；
• 安全边指两个顶点分别是森林T里两棵树中的顶点的边。安全边的加入，不会形成环。加入安全边，可将森林中的两棵树连接成一棵更大的树。

最短路径

最短路径：带权图中从源点到终点的所有路径中，所经过边的权值之和最小的路径。
图的最短路径：
单源点最短路径：从一个顶点到其余各顶点的最短路径；
每对顶点间的最短路径。

狄杰斯特拉 (Dijkstra) 算法

求解单源点最短路径的算法，通过不断更新顶点间的最短路径来实现。

当前最短路径的更新

拓扑排序

拓扑排序：在一个有向图中找一个满足所有有向边的方向的顶点序列的过程。

拓扑排序方法

1. 从有向图中选择一个没有前驱（入度为0）的顶点并输出。
2. 从图中删去该顶点及发出的全部有向边。
3. 重复以上步骤，直到所有顶点都被输出。

拓扑排序示例

计算机专业课程学习顺序的拓扑排序，展示了如何根据先修课程的要求进行排序。

课程之间的先后关系可用有向图表示：
拓扑序列：C2-C7-C1-C3-C4-C5-C6 或：C1-C2-C3-C4-C5-C7-C6 等
注意：拓扑序列不一定唯一。

总结

• 普里姆 (Prim) 算法和克鲁斯卡尔 (Kruskal) 算法构造最小生成树的方法。
• 狄杰斯特拉 (Dijkstra) 算法求解单源点最短路径。
• 拓扑排序的应用。