基本应用

最小生成树（MST）

在连通无向带权图中，找一棵包含全部顶点且边权和最小的生成树。

算法	思路	复杂度	适用
Prim	从顶点出发，每次选连接已选集合的最小边	$O(n^2)$	稠密图
Kruskal	按边权从小到大选边，用并查集判回路	$O(e\log e)$	稀疏图

算法	求解问题	复杂度	说明
Dijkstra	单源最短路径	$O(n^2)$	不能处理负权边
Floyd	每对顶点间最短路径	$O(n^3)$	可处理负权边，动态规划

对有向无环图（DAG）的顶点排序，使得每条边的起点都排在终点之前。用于检测图中是否存在环、任务调度等。每次选择一个入度为 0 的顶点输出并删除其出边。

复杂度： $O(n+e)$ 。若拓扑排序输出的顶点数少于 n，说明图中存在环。

在 AOE 网（边表示活动的带权有向图）中，从源点到汇点路径长度最长的路径称为关键路径，其上的活动是关键活动。关键路径的长度决定了工程的最短工期。

已知一个有向无环图的拓扑序列是唯一的，则此图一定是（）

(A) 强连通图 (B) 有向完全图 (C) 有向树 (D) 有向链

答案与解析

答案：(D)

有向链。拓扑序列唯一意味着图中任意两个顶点之间都有明确的先后关系，只有有向链（即所有顶点形成一条链）才能满足这个条件。

下列算法中，可用于求解单源最短路径且要求边权非负的是（）

A. Prim 算法 B. Dijkstra 算法 C. Floyd 算法 D. Kruskal 算法

答案与解析

答案：B

解析：Dijkstra 算法求解单源最短路径，要求边权非负。Floyd 可求解多源最短路径且允许负权边（但不能有负权回路）；Prim 和 Kruskal 求解的是最小生成树。

最小生成树和最短路径的常用算法有哪些？各自复杂度如何？

答案与解析

最小生成树：Prim 算法（O(n²)，适合稠密图）、Kruskal 算法（O(e log e)，适合稀疏图）。

最短路径：Dijkstra 算法（单源，O(n²)，要求边权非负）、Floyd 算法（每对顶点，O(n³)，允许负权边）。

拓扑排序的应用场景是什么？

答案与解析

拓扑排序用于有向无环图（DAG），应用场景包括：课程安排的先后顺序、工程任务的依赖调度、编译器中源文件的编译顺序、检测有向图是否存在环等。