图论算法精讲：核心概念、存储与例题

前言

图论是编程中几乎是最难同时也是最实用的算法之一，学习它是十分有必要的。本文简单介绍图论的基础知识。

简介

图论算法是计算机科学中研究图结构上各种问题的一类算法。图由顶点和边组成，用于建模对象之间的关系，是离散数学和数据结构的重要组成部分。

核心概念

图 $G=(V, E)$ 由顶点集合 $V$ 和边集合 $E$ 构成。根据边的方向性，图可分为无向图和有向图；根据边是否有权重，可分为有权图和无权图。

主要算法类别

1. 图的遍历
   • 深度优先搜索：沿着路径深入探索，用于连通性检测、拓扑排序等
   • 广度优先搜索：层层向外扩展，用于最短路径（无权图）、层序遍历等
2. 最短路径问题
   • Dijkstra 算法：求解单源最短路径（边权非负）
   • Bellman-Ford 算法：处理负权边，检测负环
   • Floyd-Warshall 算法：求解任意两点间最短路径
   • SPFA 算法：队列优化的 Bellman-Ford
3. 最小生成树
   • Prim 算法：从顶点出发逐步扩展
   • Kruskal 算法：基于边排序和并查集
4. 拓扑排序
   对有向无环图进行线性排序，用于任务调度、依赖关系分析
5. 关键路径
   求解项目的最短完成时间
6. 连通性相关
   • 强连通分量：有向图中的极大强连通子图
   • 割点与桥：删除后破坏图连通性的顶点或边
   • 并查集：高效处理连通分量合并与查询
7. 网络流
   • 最大流：求解网络中从源点到汇点的最大流量
   • 最小割：将图分为两部分的最小边权和
   • 二分图匹配：求解匹配问题

应用领域

图论算法广泛应用于社交网络分析、地图导航、电路设计、编译器优化、任务调度、推荐系统、生物信息学等众多领域，是算法竞赛和工业界面试的重点内容。

存储图的方法

这里给出一个范例图，后续代码存储的图都是它。

1. 邻接矩阵

原理

假设有 $N$ 个点，如果点 $i$ 和 点 $j$ 相连，则 $g_{i,j} = 1$（如有边权则等于边权）。

代码框架

const int MAXN = 1e6 + 5;
int g[MAXN][MAXN]; // 邻接矩阵
vector<pair<, >> edges = { {, }, {, }, {, }, {, }, {, }, {, }, {, } };
 ( &e : edges) {
     u = e.first, v = e.second;
    g[u][v] = ;
    g[v][u] = ;
}