图论基础
核心概念
| 术语 | 定义 |
|---|---|
| 顶点（节点） | 图的基本单元 |
| 边 | 连接两个顶点的连线 |
| 有向图 | 边有方向（A→B ≠ B→A） |
| 无向图 | 边没有方向 |
| 带权图 | 边有数值权重/代价 |
| 度 | 与顶点相连的边数 |
| 路径 | 由边连接的顶点序列 |
| 环 | 起点和终点相同的路径 |
| 连通图 | 任意两顶点间都有路径 |
| 树 | 连通无环无向图 |
| DAG | 有向无环图——无有向环 |
| 生成树 | 连接所有顶点的树 |
算法复杂度参考
BFS — 广度优先搜索
Time: O(V + E)
Space: O(V)
无权图中的最短路径
DFS — 深度优先搜索
Time: O(V + E)
Space: O(V)
环检测、拓扑排序
Dijkstra算法
Time: O((V+E) log V)
Space: O(V)
非负权重最短路径
Bellman-Ford算法
Time: O(V · E)
Space: O(V)
支持负权重
Floyd-Warshall
Time: O(V³)
Space: O(V²)
所有对最短路径
Kruskal最小生成树
Time: O(E log E)
Space: O(V)
最小生成树
Prim最小生成树
Time: O(E log V)
Space: O(V)
稠密图首选
拓扑排序
Time: O(V + E)
Space: O(V)
DAG顶点的线性排序