【图论基础与算法详解：从连通性到最小生成树】
摘要：本文系统讲解图论核心概念，包括图的连通性、存储结构（邻接矩阵/邻接表）、遍历算法（BFS/DFS）及最小生成树算法（Prim/Kruskal）。通过直观示例对比不同算法的时间复杂度与适用场景，帮助读者快速掌握图论基础知识。文中包含清晰的算法步骤图解、时间复杂度分析及代码实现模板，适合算法学习者和面试备考参考。
图论基础概念整理
一、连通性相关概念
1. 无向图
- 连通：若从顶点V到顶点W有路径存在，则称V和W连通
- 连通图：图中任意两个顶点都连通
- 连通分量：无向图中的极大连通子图
2. 有向图
- 强连通：若从顶点V到W和W到V都有路径
- 强连通图：图中任意两个顶点都强连通
- 强连通分量：有向图中的极大强连通子图
二、生成树
- 定义：连通图的生成树是包含所有顶点的极小连通子图
- 性质：
- 含有n个顶点的生成树有n-1条边
- 最小生成树是权值之和最小的生成树
- 最小生成树可能不唯一，但权值和相同
三、顶点度数
四、经典问题
1. 边数计算
2. 顶点度数
- 有向图中单个顶点的最大度数：2(n-1)
五、存储结构
六、遍历算法
七、最小生成树算法
注：稠密图(e≈n²)，稀疏图(e≪n²)
n个顶点e条边的图在邻接矩阵和邻接表中存储空间复杂度，时间复杂度分析及BFS算法及DFS算法时间复杂度分析
八、图的存储结构与遍历时间复杂度对比
广度优先搜索(BFS)和深度优先搜索(DFS)详解
1. BFS算法
基本思想
- 采用层序遍历方式，从起点开始逐层向外扩展
- 使用队列数据结构实现(先进先出)
- 适合求解最短路径问题(无权图)
算法步骤
- 将起始顶点入队并标记为已访问
- 从队列取出一个顶点并访问
- 将该顶点的所有未访问邻接顶点入队
- 重复步骤2-3直到队列为空
时间复杂度
示例
A / \\ B C / \\ \\ D E F BFS顺序：A → B → C → D → E → F
解释：
访问A，将B、C入队 → 队列：[B, C]
访问B，将D、E入队 → 队列：[C, D, E]
访问C，将F入队 → 队列：[D, E, F]
依次访问D、E、F。
2. DFS算法
基本思想
- 采用深度优先策略，沿路径尽可能深入
- 使用栈数据结构实现(递归或显式栈)
- 适合求解连通性、拓扑排序等问题
算法步骤
- 从起始顶点出发并标记为已访问
- 选择一个未访问的邻接顶点递归访问
- 若无未访问邻接顶点则回溯
时间复杂度
示例
A / \\ B C / \\ \\ D E F DFS顺序：A → B → D → E → C → F
解释：
访问A，选择B → 访问B，选择D → 访问D（无法继续，回溯到B）。
从B选择E → 访问E（回溯到B→A）。
从A选择C → 访问C，选择F → 访问F。
最小生成树(MST)算法详解
1. Prim算法
算法原理
- 贪心策略：从一个起点开始，像滚雪球一样慢慢扩大已连接的顶点集合，每次选择连接\"已连部分\"和\"未连部分\"的最便宜的边。
- 数据结构：
- 使用优先队列(最小堆)存储候选边
- 用数组标记已选顶点
- 执行过程：
- 从任意顶点开始，初始化已选集合U={v}
- 不断选择U到V-U的最小权值边，将新顶点加入U
- 直到U包含所有顶点
时间复杂度
- 邻接矩阵：O(V²)
- 优先队列优化：O(ElogV)
示例演示
2 A-------B | \\ / | 3| \\ / |4 | X | | / \\ | C-------D 5步骤：
- 从A开始，U={A}，候选边AB(2), AC(3), AD(∞)
- 选择AB(2)，U={A,B}，新增候选边BC(1), BD(4)
- 选择BC(1)，U={A,B,C}，新增候选边CD(5)
- 选择BD(4)，U={A,B,C,D}
生成树：AB(2) + BC(1) + BD(4)，总权重=7
2. Kruskal算法
算法原理
- 核心思想：把所有边按价格从低到高排序，依次选择，只要不形成环路就加入
- 数据结构：
- 使用并查集(Union-Find)检测环路
- 需要对所有边排序
- 执行过程：
- 将所有边按权值升序排序
- 依次选择最小边，若不形成环则加入生成树
- 直到选择V-1条边
时间复杂度
- 主要开销在排序：O(ElogE)
示例演示
使用同Prim算法的图：
边排序：[BC(1), AB(2), AC(3), BD(4), CD(5)]
步骤：
- 选择BC(1)，不形成环
- 选择AB(2)，不形成环
- 选择AC(3)，会形成环ABC，跳过
- 选择BD(4)，不形成环
生成树：BC(1) + AB(2) + BD(4)，总权重=7
