图论是计算机科学中最基础也最实用的分支之一，从社交网络分析到路径导航，从项目调度到电路设计都离不开图论知识。本文整理简单图论的核心概念和常用算法，适合入门学习梳理脉络。
一、基础概念入门
1. 图的定义
图由顶点集V和边集E组成，记作G=(V, E)，根据边的方向可以分为两类：
无向图：边没有方向，
(u,v)和(v,u)是同一条边有向图：边有方向，
<u,v>表示从u指向v的单向边
简单图是最基础的图类型，满足两个条件：没有重复边，不存在顶点到自身的环，也是日常算法题和工程中最常用的图结构。
2. 核心概念梳理
概念 | 含义 |
|---|---|
度 | 顶点连接的边数，无向图中直接计数，有向图分为入度和出度 |
路径 | 从一个顶点到另一个顶点经过的顶点序列，路径中不重复顶点称为简单路径 |
连通性 | 任意两个顶点之间都存在路径称为连通图，不连通的图分为多个连通分支 |
圈 | 起点和终点是同一个顶点的路径，根据长度分为奇圈和偶圈 |
完全图 | 任意两个顶点之间都有一条边相连，n个顶点的完全图有 |
二分图 | 顶点可以分成两个不相交的集合，所有边都连接两个集合的顶点，不存在集合内部的边；一个图是二分图的充要条件是不含奇圈 |
3. 图的存储方式
入门阶段最常用两种存储方式，根据场景选择：
邻接矩阵：用二维数组存储，
g[i][j]表示i到j的边权重，适合稠密图，查询速度O(1)，缺点是空间复杂度O(n²)，n较大时浪费空间邻接表：用数组+链表存储，每个顶点对应一个链表保存相连的顶点和权重，适合稀疏图，空间复杂度O(n+m)，遍历更高效，是算法题中最常用的存储方式
二、最短路核心算法
最短路是图论中最常用的算法，目标是找到源点到目标点权重最小的路径，入门阶段需要掌握四种常见算法：
1. Dijkstra算法
适用场景：所有边权重都是非负数的单源最短路问题，分为朴素版和堆优化版：
朴素版：时间复杂度O(n²)，适合稠密图，核心思路是贪心，每次选当前距离源点最近的未处理顶点，然后松弛所有相邻边
// 朴素版Dijkstra核心代码
int dijkstra() {
memset(d, 0x3f3f3f, sizeof(d));
d = 0; // 源点初始距离为0
for(int i = 0; i < n; i++) {
// 找未访问的距离最小的顶点
int t = -1;
for(int j = 1; j <= n; j++) {
if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
}
st[t] = 1;
// 松弛所有相邻边
for(int j = 1; j <= n; j++) {
d[j] = min(d[j], d[t] + g[t][j]);
}
}
return d[n] >= 0x3f3f3f ? -1 : d[n];
}
堆优化版：时间复杂度O(mlogn)，适合稀疏图，用优先队列维护距离最小的顶点，减少每次找最小值的时间开销。
核心思想松弛操作：对边(u,v)，如果满足d[u] + w(u,v) < d[v]，就更新d[v] = d[u] + w(u,v)，这是所有最短路算法的核心操作。
2. Bellman-Ford算法
适用场景：可以处理负权边，还能检测图中是否存在负环，支持带边数限制的最短路问题，时间复杂度O(nm)： 核心思路是对所有边进行n-1次松弛，因为从源点到任意点的最短路径最多包含n-1条边；如果n-1次松弛后还能继续更新距离，说明图中存在负环。
3. SPFA算法
适用场景：Bellman-Ford的队列优化版本，平均时间复杂度O(m)，最坏情况退化到O(nm)，实际工程中常用，同样可以处理负权和检测负环： 核心思路是只有松弛成功的顶点才会把相邻顶点加入队列，避免无效的松弛操作，用计数的方式检测负环：如果某个顶点入队次数超过n次，说明存在负环。
4. Floyd算法
适用场景：求任意两个顶点之间的最短路，时间复杂度O(n³)，适合顶点数不多的全源最短路问题，代码非常简洁，核心是动态规划思路：d[k][i][j]表示从i到j经过编号不超过k的顶点的最短路，递推公式：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。
三、最小生成树算法
最小生成树是连通无向图中，总权重最小的生成树（包含所有顶点，边数为顶点数-1），常用两种算法：
1. Prim算法
思路类似Dijkstra，每次选当前距离生成树集合最近的顶点加入集合，然后更新其他顶点到集合的距离，朴素版时间复杂度O(n²)，堆优化版O(mlogn)，适合稠密图。
2. Kruskal算法
思路是贪心排序：先把所有边按权重从小到大排序，然后依次选边，用并查集判断两个顶点是否已经连通，如果不连通就把这条边加入生成树，直到选够n-1条边，时间复杂度O(mlogm)，适合稀疏图，实现更简单。
四、二分图核心知识
二分图是一类特殊的图，核心问题有两个：
1. 二分图判定
用染色法（黑白染色）判定：从任意顶点开始，把它染成黑色，相邻顶点染成白色，如果遍历过程中发现相邻顶点颜色相同，说明不是二分图，时间复杂度O(n+m)。
2. 二分图最大匹配
最常用匈牙利算法，核心思路是不断给左部顶点找增广路，找到一条增广路匹配数就加1，时间复杂度O(nm)，可以解决很多匹配类问题，比如工作安排、配对问题。
五、入门学习建议
先掌握基础概念和存储方式，再逐个突破算法，不要跳步，每个算法都动手实现一遍，比只看理解深刻得多
结合算法题练习，比如最短路、最小生成树都是经典的算法题考点，刷对应题目巩固知识
理解每个算法的适用场景，遇到问题能快速选择合适的算法，比如非负权单源最短路用Dijkstra，带负权用SPFA，全源用Floyd。
简单图论是算法和工程的基础，入门难度不高，掌握核心算法就能解决绝大多数常见问题，重点还是多动手实现、多做题练习。 </doc_start> 以上是整理的简单图论入门学习内容，适合入门学习者梳理核心知识点，如需补充代码细节或拓展其他内容可继续提出。