考研核心考点#

• 算法思想：基于贪心策略，每次从尚未确定最短路径的顶点集合中，选择距离源点最近的顶点，通过该顶点松弛其他顶点的最短路径估计值，重复此过程直到所有顶点都被访问。
• 适用限制：仅适用于边权非负的单源最短路径问题，无法处理存在负权边或负权环的场景，与Bellman-Ford、Floyd算法形成场景区分。
• 复杂度分析：邻接矩阵实现下时间复杂度为$O(V^2)$，适合稠密图；使用优先队列（堆）优化邻接表实现时，时间复杂度为$O((V+E)\log V)$，适配稀疏图场景，是考研高频考察的优化版本。
• 常考题型：给定带权无向/有向图，手动模拟算法执行过程，推导源点到各顶点的最短路径长度与路径细节。

考研核心考点#

共两种经典求解算法，考察重点为两种算法的对比与手动模拟：

1. Prim算法：从单个源顶点出发，每次选择连接当前生成树与外部顶点的最小权边，逐步扩展生成树。邻接矩阵实现复杂度$O(V^2)$适合稠密图，堆优化版本复杂度$O(E\log V)$适合稀疏图。
2. Kruskal算法：将所有边按权值从小到大排序，依次选择不形成环的边加入生成树，借助并查集快速判断环的存在。复杂度主要由排序决定，为$O(E\log E)$，适合稀疏图。

• 额外考点：最小生成树的唯一性判断（当存在多条权值相同的边且选择顺序不同时可能出现多解）、最小生成树的总权值性质。
• 常考题型：手动模拟两种算法的执行过程，对比两种算法的适用场景与步骤差异。

考研核心考点#

• 核心概念：基于AOE网（边表示活动、顶点表示事件），关键路径是从源点到汇点的最长路径，其总长度决定了工程的最短完成工期。
• 关键参数：
  • $ve[i]$：顶点$i$的最早发生时间（拓扑排序正向递推）
  • $vl[i]$：顶点$i$的最晚发生时间（逆拓扑排序反向递推）
  • 活动$a$的最早开始时间$e(a)=ve[u]$（$u$为活动起点顶点）
  • 活动$a$的最晚开始时间$l(a)=vl[v]-len(a)$（$v$为活动终点顶点，$len(a)$为活动权值）
  • 活动余量$l(a)-e(a)$，余量为0的活动为关键活动，全部关键活动组成关键路径。
• 常考题型：给定AOE网，手动计算各顶点的$ve$、$vl$值，推导各活动的$e$、$l$值，找出所有关键路径与工程最短工期。