图算法是图论和组合优化中的核心内容。以下是主要的图算法分类： # 1. 遍历算法 **基础的图探索方法** - **深度优先搜索（DFS）**：沿路径深入，回溯 - **广度优先搜索（BFS）**：按层次扩展 - 应用：连通性判断、拓扑排序、寻找环 # 2. 最短路径算法 **寻找两点间最优路径** - **Dijkstra算法**：单源最短路径（非负权重） - **Bellman-Ford算法**：可处理负权边 - **Floyd-Warshall算法**：所有点对最短路径 - **A*算法**：启发式搜索 - 应用：导航系统、网络路由 # 3. 最小生成树算法 **连接所有节点的最小代价方案** - **Kruskal算法**：按边权重排序 - **Prim算法**：从一个顶点开始扩展 - **Borůvka算法**：并行化友好 - 应用：网络设计、聚类分析 # 4. 网络流算法 **研究网络中的流量问题** - **Ford-Fulkerson方法**：最大流 - **Edmonds-Karp算法**：最大流的BFS实现 - **最小费用流**：考虑成本的流 - **最大匹配**：二分图匹配 - 应用：任务分配、运输优化 # 5. 连通性算法 **分析图的结构特性** - **强连通分量**：Tarjan算法、Kosaraju算法 - **割点和桥**：找关键节点和边 - **双连通分量**：容错性分析 - 应用：网络可靠性、社交网络分析 # 6. 着色算法 **分配标签避免冲突** - **贪心着色**：简单但不保证最优 - **Welsh-Powell算法**：按度数排序 - **回溯法**：精确解 - 应用：调度问题、寄存器分配 # 7. 特殊路径算法 **满足特定条件的路径** - **欧拉路径/回路**：经过每条边一次 - **哈密尔顿路径/回路**：经过每个顶点一次（[旅行商问题 TSP](旅行商问题%20TSP.md)） - **中国邮递员问题**：最短闭合路径 - 应用：路线规划、DNA测序 # 8. 社区发现算法 **找出图中的聚类结构** - **Girvan-Newman算法**：基于边介数 - **Louvain算法**：模块度优化 - **谱聚类**：基于图的拉普拉斯矩阵 - 应用：社交网络、推荐系统 # 9. 中心性算法 **评估节点重要性** - **度中心性**：连接数 - **介数中心性**：路径经过频率 - **接近中心性**：到其他节点的距离 - **[pageRank 算法](pageRank%20算法)**：网页排名 - 应用：影响力分析、关键节点识别 # 10. 动态规划类 **复杂图问题的优化** - **树形DP**：树结构上的动态规划 - **状压DP**：用位运算处理状态 - **区间DP**：处理区间问题 - 应用：优化问题、游戏策略 # 实际应用领域 - **社交网络**：好友推荐、影响力传播 - **交通物流**：路径规划、配送优化 - **互联网**：网页排名、网络路由 - **生物信息**：蛋白质相互作用、基因网络 - **电路设计**：布线、优化 这些算法构成了解决实际图问题的工具箱，选择哪个算法取决于具体问题的特征和约束。