图论

基础图论

基础图论包含了处理图的基本算法和遍历方式。

特点

1. 时间复杂度：从 到 不等
2. 空间复杂度：通常为 或
3. 适用于网络、路径、连通性等问题

分类

DFS	深度优先搜索
BFS	广度优先搜索
拓扑排序	有向无环图排序
强连通分量	有向图连通性

最短路径

最短路径算法用于求解图中两点间的最短距离。

特点

1. 时间复杂度：从 到 不等
2. 空间复杂度：通常为 或
3. 适用于路径规划、网络流量等问题

分类

生成树

生成树算法用于求解图的最小生成树。

特点

1. 时间复杂度：通常为
2. 空间复杂度：通常为
3. 适用于网络设计、电路布线等问题

分类

应用场景对比

基础图论适合：

1. 图的遍历
2. 连通性判断
3. 环路检测
4. 拓扑序列

最短路径适合：

1. 导航系统
2. 网络路由
3. 社交网络
4. 资源调度

生成树适合：

1. 网络设计
2. 电路布线
3. 集群连接
4. 成本优化

选择建议

1. 遍历问题选择DFS/BFS
2. 单点路径选择Dijkstra
3. 全局路径选择Floyd
4. 最小代价选择Kruskal/Prim
5. 负权边选择Bellman-Ford