目录
一、图的基本概念与分类
1.1 什么是图？
图（Graph）是由顶点（Vertex）和边（Edge）组成的非线性数据结构，用于表示对象之间的复杂关系。在计算机科学中，图被广泛应用于社交网络、交通系统、网络拓扑等场景。
图的基本组成元素：
顶点（Node/Vertex）：表示实体对象
边（Edge）：表示顶点之间的关系
权重（Weight）：边可以带有权值，表示关系的强度或成本
1.2 图的分类体系
（1）按方向性分类
无向图（Undirected Graph）：
边没有方向性
表示双向关系
邻接矩阵对称
示例：社交网络中的好友关系
有向图（Directed Graph/Digraph）：
边有明确方向
表示单向关系
邻接矩阵不对称
示例：网页链接关系
（2）按权重分类
无权图：
边没有权值
只表示连接关系
示例：迷宫路径
带权图（Weighted Graph）：
边有权值
表示关系的强度或成本
示例：城市间距离
（3）按连通性分类
连通图（Connected Graph）：
任意两顶点间都有路径
无向图的特殊情况
强连通图（Strongly Connected Graph）：
有向图中任意两顶点双向可达
示例：某些通信网络
非连通图（Disconnected Graph）：
存在孤立顶点或子图
示例：岛屿分布图
（4）特殊图类型
树（Tree）：
无环连通无向图
n个顶点有n-1条边
示例：组织结构图
二分图（Bipartite Graph）：
顶点可分为两个不相交集合
所有边连接两个集合中的顶点
示例：求职者与职位匹配
完全图（Complete Graph）：
每对顶点之间都有边相连
边数为n(n-1)/2（无向图）
示例：小型社交圈
二、图的存储结构详解
2.1 邻接矩阵（Adjacency Matrix）
实现原理：
使用二维数组matrix[u][v]表示顶点u和v之间的边关系。
cpp
const int MAXN = 1000;
int adjMatrix[MAXN][MAXN]; // 邻接矩阵
// 初始化
void initMatrix() {
memset(adjMatrix, 0, sizeof(adjMatrix));
}
// 添加边
void addEdge(int u, int v, int w = 1) {
adjMatrix[u][v] = w;
// 无向图需要对称添加
// adjMatrix[v][u] = w;
}性能分析：
空间复杂度：O(V²)
查询边存在：O(1)
遍历邻接点：O(V)
适用场景：
稠密图（边数接近顶点数平方）
需要频繁查询边存在性
图规模不大（V<1000）
2.2 邻接表（Adjacency List）
实现原理：
为每个顶点维护一个链表，存储其邻接顶点。
cpp
#include <vector>
using namespace std;
const int MAXN = 100000;
vector<int> adjList[MAXN]; // 无权图邻接表
// 带权图邻接表
struct Edge {
int to, weight;
};
vector<Edge> adjListW[MAXN];
// 添加边
void addEdge(int u, int v, int w = 1) {
adjList[u].push_back(v);
// 无向图需要双向添加
// adjList[v].push_back(u);
// 带权图添加
// adjListW[u].push_back({v, w});
}性能分析：
空间复杂度：O(V+E)
查询边存在：O(degree(u))
遍历邻接点：O(degree(u))
适用场景：
稀疏图
大规模图（V>10000）
需要频繁遍历邻接点
2.3 边集数组（Edge List）
实现原理：
简单存储所有边的集合。
cpp
struct Edge {
int from, to, weight;
};
vector<Edge> edges;适用场景：
Kruskal等需要处理所有边的算法
对存储顺序有特殊要求的场景
2.4 链式前向星
实现原理：
使用数组模拟链表，结合了邻接表和边集数组的优点。
cpp
const int MAXE = 100000;
struct Edge {
int to, w, next;
} edges[MAXE];
int head[MAXN], edgeCnt;
void init() {
memset(head, -1, sizeof(head));
edgeCnt = 0;
}
void addEdge(int u, int v, int w) {
edges[edgeCnt] = {v, w, head[u]};
head[u] = edgeCnt++;
}优势：
内存连续，缓存友好
适合竞赛编程
三、图论核心算法深度解析
3.1 深度优先搜索（DFS）算法
算法思想：
尽可能深地探索图的分支，直到无法继续前进才回溯。
实现代码：
cpp
vector<bool> visited(MAXN, false);
void dfs(int u) {
visited[u] = true;
// 处理顶点u
for (int v : adjList[u]) {
if (!visited[v]) {
dfs(v);
}
}
}应用场景：
连通分量检测
拓扑排序（有向无环图）
寻找图中环路
解决迷宫问题
时间复杂度：O(V+E)
3.2 广度优先搜索（BFS）算法
算法思想：
逐层扩展探索，先访问离起点近的顶点。
实现代码：
cpp
void bfs(int start) {
queue<int> q;
vector<bool> visited(MAXN, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
// 处理顶点u
for (int v : adjList[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}应用场景：
无权图最短路径
社交网络中的"好友推荐"
网页爬虫
网络广播
时间复杂度：O(V+E)
3.3 Dijkstra最短路径算法
算法思想：
贪心策略，每次选择当前距离起点最近的顶点进行松弛操作。
实现代码：
cpp
void dijkstra(int start) {
vector<int> dist(MAXN, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto &e : adjListW[u]) {
int v = e.to;
int w = e.weight;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}适用条件：
无负权边
有向/无向图均可
时间复杂度：
普通实现：O(V²)
优先队列优化：O(E + VlogV)
3.4 Floyd-Warshall算法
算法思想：
动态规划，逐步允许通过更多顶点作为中转点。
实现代码：
cpp
void floyd() {
int dist[MAXN][MAXN];
// 初始化
for (int i = 0; i < MAXN; ++i) {
for (int j = 0; j < MAXN; ++j) {
dist[i][j] = (i == j) ? 0 : INT_MAX;
}
}
// 添加边
// ...
// 核心算法
for (int k = 0; k < MAXN; ++k) {
for (int i = 0; i < MAXN; ++i) {
for (int j = 0; j < MAXN; ++j) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}特点：
多源最短路径
可处理负权边（不能有负权环）
代码简洁
时间复杂度：O(V³)
3.5 拓扑排序算法
算法思想：
将有向无环图（DAG）的顶点排成线性序列，使得对每条边(u,v)，u在v前面。
Kahn算法实现：
cpp
vector<int> topoSort(int n) {
vector<int> inDegree(n, 0);
queue<int> q;
vector<int> result;
// 计算入度
for (int u = 0; u < n; ++u) {
for (int v : adjList[u]) {
inDegree[v]++;
}
}
// 入度为0的顶点入队
for (int u = 0; u < n; ++u) {
if (inDegree[u] == 0) {
q.push(u);
}
}
// 拓扑排序
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : adjList[u]) {
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
return result.size() == n ? result : vector<int>();
}应用场景：
任务调度
课程安排
依赖关系解析
四、图论在现实中的应用
4.1 社交网络分析
顶点表示用户
边表示好友关系
应用：好友推荐、社区发现
4.2 交通网络优化
顶点表示车站/路口
边表示路线
应用：最短路径导航
4.3 网络拓扑管理
顶点表示网络设备
边表示连接
应用：路由优化
4.4 知识图谱构建
顶点表示实体
边表示关系
应用：智能搜索
五、洛谷图论入门题目精选
5.1 P5318 【深基18.例3】查找文献
标签：图的遍历、DFS、BFS
难度：普及-
解题要点：
使用邻接表存储图
需要对邻接点排序以满足题目要求
分别实现DFS和BFS
5.2 P3916 图的遍历
标签：反向图、DFS
难度：普及/提高-
解题要点：
反向建图技巧
从编号大的顶点开始遍历
记忆化优化
5.3 P1339 [USACO09OCT]Heat Wave G
标签：最短路径、Dijkstra
难度：普及/提高-
解题要点：
标准Dijkstra算法实现
优先队列优化
邻接表存储
5.4 P3366 【模板】最小生成树
标签：Kruskal、Prim
难度：普及
解题要点：
两种最小生成树算法实现
并查集在Kruskal中的应用
优先队列在Prim中的应用
5.5 P2661 信息传递
标签：基环树、DFS
难度：提高
解题要点：
识别图中的最小环
DFS标记深度
时间戳技巧
六、图论学习建议
基础先行：先掌握图的存储和基本遍历
循序渐进：从简单题目开始，逐步提高难度
理解本质：不要死记硬背算法，理解其核心思想
多实践：通过大量练习培养图论思维
总结归纳：建立自己的解题模式库
图论作为算法竞赛和计算机科学的核心内容，需要长期的学习和积累。