全部文章

页码10/11

Prim 算法

Prim 是求解最小生成树的算法，从任意顶点出发维护一个已选顶点集合，每次选取连接集合内外、权值最小的边，将对应顶点并入集合，直到包含全部顶点；朴素实现 O(n^2) 适合稠密图，堆优化版本 O(mlog n) 适合稀疏图，支持负权边。

给定图中起点 s 与终点 t，判断是否存在一条从顶点 s 到顶点 t 的路径，通常可用深度优先搜索或广度优先搜索求解，有路径则 t 从 s 可达，否则不可达。

SPFA 是 Bellman‑Ford 的队列优化版本，用于求解带负权边的单源最短路径，只将被松弛成功的顶点入队，避免无效松弛；通过记录顶点入队次数，若某点入队超过顶点总数，即可判定存在负权回路，平均时间复杂度较低，最坏仍为 O (nm)。

Kruskal 是求解最小生成树的算法，核心思路是将全部边按权值从小到大排序，依次选取边，借助并查集判断边的两个端点是否属于不同连通块，若不连通就把这条边加入生成树，直到选出 n‑1 条边；适合稀疏图，时间复杂度主要由排序决定 O(mlog m)，可以处理带负权的边。

插入排序的核心思想是将数组分为已排序和未排序两部分，依次取出未排序部分的元素，向前遍历已排序部分找到合适位置插入，不断扩大有序区间直至整个数组有序，适合小规模数据，时间复杂度最坏为 O (n²)。

归并排序采用分治思想，先把数组不断对半拆分成子数组，对子数组排序后，再将两个有序子数组合并为一个有序数组；时间复杂度稳定为 O (nlogn)，需要额外辅助空间，是稳定排序算法。

二部图判断即检验图能否把顶点划分成两个互不相交集合，使得每条边的两个端点分别属于不同集合，不存在同一集合内部的边；可通过 BFS 或 DFS 进行染色，若发现相邻顶点颜色相同则不是二部图，无冲突则为二部图。

最小生成树两大理论基础：1. 切分性质：任意割的权值最小割边，必属于某棵最小生成树，是 Prim 算法的依据。2. 环性质：任意环中权值最大的边，一定不在最小生成树里，支撑 Kruskal 算法。连通加权无向图才存在最小生成树，总权值和唯一，可有多棵不同最小生成树。