Skip to main content

1 / 4概念

Graph Algorithms

图算法把“点与点之间怎么走”变成可计算的顺序:先定义状态和边权,再选遍历、最短路或生成树。判断标准不是“算法名字熟不熟”,而是图是否有负权、是否稠密、要单源还是全源、要不要生成树。

1 概念​

1.1 一句话定义​

图算法是在顶点集合 V 和边集合 E 上,按某种不变量逐步扩展已知信息的算法。最短路维护“从源点到每个点的最小代价”,最小生成树维护“连接所有点的最小总边权”,拓扑排序维护“所有边都从前往后”的线性序。

1.2 它解决什么问题​

  • 导航与网络:路由、地图、社交关系、依赖解析都建模成图。
  • 依赖顺序:构建系统、包管理、任务调度需要拓扑排序发现环。
  • 成本最小化:网络布线、聚类、近似算法需要最小生成树。
  • 状态搜索:游戏、规划、拼图把状态当点、动作当边,用 BFS/A* 找最短动作序列。

没有图模型,这些问题只能写成针对具体场景的嵌套循环,复用性和正确性都不可控。

1.3 不属于本页的内容​

主题去哪
邻接矩阵、邻接表、CSR、并查集Graph Structures
渐进记号、递归式、摊还分析Complexity Analysis
排序与二分Sorting & Searching
堆与优先队列的实现Trees & Heaps
NP 完全性与不可解性Computational Complexity

1.4 关键术语​

术语含义容易混淆的点
有向图 / 无向图边是否有方向无向边通常存两条有向边
权重边上的代价,可为负负权不等于负环
负环总权为负的环有负环时最短路无下界
单源 / 全源一个起点 / 所有点对全源可由多次单源得到
松弛用 dist[u] + w 更新 dist[v]松弛顺序决定算法正确性
DAG有向无环图DAG 上最短路可带负权
生成树连接所有点的无环子图最小生成树不保证最短路
割把点集分成两部分的边集合割边不一定唯一
启发式对剩余代价的估计可采纳不等于一致
稠密 / 稀疏E 接近 V² / E 接近 V选择矩阵还是邻接表