信息技术大学
图进阶
数据结构与算法·面试高频 · 第 2 章 树与图
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
图进阶
数据结构与算法·面试高频 · 第 2 章 树与图
并查集
合并与查询同阵营：路径压缩加按秩合并，近似 O(1) 的朋友圈管理。
find
一路找根，路径压缩顺手拍平
union
两根相连，按秩挂树不疯长
判连通
同根即同阵营，朋友圈与岛屿变体通用
复杂度
α(n) 反阿克曼，实践视作常数
Dijkstra 最短路
非负边权的单源最短路：贪心定型，优先队列取当前最近的扩张。
贪心本质
每次锁定未定节点中距离最小者
松弛
经新节点中转更近，就更新邻居距离
堆优化
优先队列取最小，O((n+m) log n)
前提
边权非负；负权换 Bellman-Ford
最小生成树
连通所有点的边权和最小：Kruskal 排边加并查集，Prim 就地扩张。
Kruskal
边升序逐条试，并查集判不成环才要
Prim
从一点长出树，堆里挑最短的跨界边
应用
网络布线、聚类分割的底座
二分图判定
染色法分两拨：相邻不同色，染得下去是二分图，撞色就有奇环。
染色
BFS/DFS 相邻节点染异色
判据
撞色即存在奇环，非二分图
应用
队伍划分、二部匹配的前置
本节要点
- ✓并查集：压缩加按秩，近 O(1)
- ✓Dijkstra 贪心加堆，非负边权专属
- ✓最小生成树：Kruskal 排边判环
- ✓二分图：染色撞色定奇环
延伸主题：手写并查集模板刷网络延迟时间
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1Dijkstra 为什么不能处理负权边？
参考答案它靠「出队即定型」的贪心：负权会让后到的路径反而更短，已定型节点可能被再次改善，贪心前提崩塌。负权要用 Bellman-Ford 逐步松弛。
2Kruskal 与 Prim 怎么选？
参考答案Kruskal 全局排边、并查集判环，稀疏图实现简单；Prim 从点长树、堆挑跨界边，稠密图更划算。两者都是「安全边」贪心，输赢在输入形态。
3并查集为什么两个优化都要上？
参考答案只路径压缩，最坏仍可能长链；只按秩合并，查询链也可能深。两者叠加才有 α(n) 近常数的保证——单优化是改善，双优化是质变。