基本应用

最小生成树(MST)

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

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

最短路径

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

拓扑排序

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

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

关键路径

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

习题

习题 1

已知一个有向无环图的拓扑序列是唯一的,则此图一定是( )

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

拓扑排序有向无环图有向链拓扑序列唯一性

解题思路:

本题由拓扑序列唯一反推图的结构。思路是:拓扑序列唯一意味着任意两个顶点之间都存在确定的先后依赖关系,而这种全局的严格顺序只有把所有顶点串成一条链时才能成立。

详细步骤:

  1. 拓扑序列唯一,说明图中任意两个顶点之间都存在明确的先后关系,不存在可以自由交换位置的独立顶点。
  2. 若图中存在有向链以外的结构(例如有向树的分叉或有向完全图),就会有两个互不受约束的顶点,其相对次序可以交换,从而出现多个拓扑序列。
  3. 因此只有所有顶点形成一条链的有向链,才能保证拓扑序列唯一,对应选项 (D)。

最终答案:

D(有向链)。

习题 2

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

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

单源最短路径迪杰斯特拉算法边权非负算法适用性

解题思路:

本题考查最短路径算法的适用范围。思路是按四个算法各自解决的问题分类:Prim 与 Kruskal 属于最小生成树,Floyd 属于多源最短路径且允许负权边,只有 Dijkstra 恰是单源最短路径且要求边权非负。

详细步骤:

  1. Dijkstra 算法求解单源最短路径,且要求边权非负,选项 B 正确。
  2. Floyd 算法求解每对顶点之间的最短路径,允许负权边(但图中不能有负权回路),不符合“单源”要求。
  3. Prim 算法和 Kruskal 算法求解的是最小生成树,解决的是连通所有顶点且总权值最小的问题,与最短路径无关。

最终答案:

B。

习题 3

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

最小生成树最短路径普里姆算法迪杰斯特拉算法

解题思路:

本题考查最小生成树与最短路径的常用算法及其复杂度。答题时按两类问题分别列举:最小生成树给出 Prim 与 Kruskal 及其稠密/稀疏适用性,最短路径给出 Dijkstra 与 Floyd 及其单源/每对顶点的差别。

详细步骤:

  1. 最小生成树方面:Prim 算法复杂度为 O(n2)O(n^2),适合稠密图;Kruskal 算法复杂度为 O(elog⁡e)O(e \log e),适合稀疏图。
  2. 最短路径方面:Dijkstra 算法求解单源最短路径,复杂度为 O(n2)O(n^2),要求边权非负。
  3. Floyd 算法求解每对顶点之间的最短路径,复杂度为 O(n3)O(n^3),允许负权边(但不能有负权回路)。

最终答案:

最小生成树:Prim 算法(O(n²),适合稠密图)、Kruskal 算法(O(e log e),适合稀疏图)。最短路径:Dijkstra 算法(单源,O(n²),要求边权非负)、Floyd 算法(每对顶点,O(n³),允许负权边)。

习题 4

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

拓扑排序有向无环图依赖调度环检测

解题思路:

本题考查拓扑排序的适用前提与典型应用场景。思路是先点明拓扑排序只对有向无环图有意义,再把它的作用归纳为“按依赖关系排出一个合法先后次序”,并列举相应场景。

详细步骤:

  1. 拓扑排序用于有向无环图(DAG),按各顶点的入度为零与否逐步输出顶点,从而得到一个满足所有有向边先后关系的线性序列。
  2. 课程安排的先后顺序:先修课必须排在后续课程之前。
  3. 工程任务的依赖调度、编译器中源文件的编译顺序都属于同一类“先决条件在前”的场景。
  4. 此外,若在拓扑排序过程中找不到入度为零的顶点,说明图中存在回路,因此拓扑排序还可用于检测有向图是否存在环。

最终答案:

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

发现内容有问题?

告诉我们哪里需要改进。