第十三章 图的基本概念
图，说实话，是数据结构里最灵活、也最让人头疼的东西。树你还能找到根，链表你还能找到头，图呢？它可能没有起点，也没有终点，节点之间爱怎么连就怎么连。我第一次接触图的时候，脑子里就一个想法——这玩意儿怎么存？怎么遍历？
别急，咱们一步步来。这一章我会把图的定义、分类、存储方式、遍历方法都讲清楚。你跟着我的思路走，保证能拿下。
13.1 图的定义
图，说白了就是一堆顶点（Vertex）和一堆边（Edge）的集合。用数学语言说：G = (V, E)，其中 V 是顶点集合，E 是边的集合。
举个例子：你和你朋友之间的关系网。每个人是一个顶点，两个人认识就有一条边。就这么简单。
核心要素：
- 顶点（Vertex）：图中的节点，也叫结点。
- 边（Edge）：连接两个顶点的线，表示它们之间的关系。
- 度（Degree）：一个顶点关联的边的数量。
我在项目中遇到过一个问题：用图来表示城市之间的航班路线。每个城市是一个顶点，两个城市之间有直飞航班就加一条边。当时我就在想，这图要是大了，怎么存才高效？嗯，这就是后面要讲的存储问题了。
13.2 有向图与无向图
图分两种：有向图和无向图。区别就一个字——方向。
13.2.1 无向图
边没有方向。比如你和你的好朋友，你认识他，他也认识你。这种关系是对称的。在无向图中，边 (u, v) 和 (v, u) 是同一个东西。
13.2.2 有向图
边有方向。比如微博的关注关系——你关注了某大V，但大V不一定关注你。这种关系是不对称的。在有向图中，边 <u, v> 表示从 u 指向 v，和 <v, u> 完全不同。
我个人的习惯：写代码前先想清楚图是有向还是无向。这个决定了后面存储和遍历的逻辑。有一次我忘了区分，结果遍历时把有向图当无向图处理，数据全乱了。嗯，血的教训。
13.3 图的存储
图怎么存进计算机？两种主流方式：邻接矩阵和邻接表。我两种都用过，各有优劣。
13.3.1 邻接矩阵
用一个二维数组来存。假设有 n 个顶点，就开一个 n×n 的矩阵。matrix[i][j] = 1 表示顶点 i 到顶点 j 有边，0 表示没有。
// 邻接矩阵示例 - 无向图
#define MAX_V 100
int graph[MAX_V][MAX_V] = {0};
// 添加边 (u, v)
void add_edge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1; // 无向图要加双向
}
// 检查是否有边
int has_edge(int u, int v) {
return graph[u][v];
}优点：判断两点之间是否有边，O(1) 时间，快得很。
缺点：空间复杂度 O(n²)，顶点多了就炸。10000个顶点，矩阵大小是 10000×10000，内存直接爆。
13.3.2 邻接表
每个顶点维护一个链表，链表中存的是它相邻的顶点。说白了，就是「谁跟我连着，我就记下谁」。
// 邻接表示例 - 有向图
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next;
} Node;
Node* adj_list[MAX_V];
// 添加有向边 u -> v
void add_edge(int u, int v) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = adj_list[u];
adj_list[u] = new_node;
}
// 遍历顶点 u 的所有邻居
void print_neighbors(int u) {
Node* cur = adj_list[u];
while (cur) {
printf("%d ", cur->vertex);
cur = cur->next;
}
}我建议：如果图比较稀疏（边数远小于 n²），用邻接表。如果图比较稠密（边数接近 n²），用邻接矩阵。你想想看，一个社交网络，每个人平均认识几百个人，但总用户有几千万，用邻接矩阵？那得多少内存啊。
13.4 图的遍历
遍历图，说白了就是把所有顶点都走一遍。两种经典方法：DFS（深度优先）和 BFS（广度优先）。
13.4.1 深度优先搜索（DFS）
从一个顶点出发，沿着一条路走到黑，走不动了就回头。像走迷宫一样，一条道走到死，再退回来换条路。
// DFS 递归实现
int visited[MAX_V] = {0};
void dfs(int u) {
visited[u] = 1;
printf("访问顶点: %d\n", u);
Node* cur = adj_list[u];
while (cur) {
if (!visited[cur->vertex]) {
dfs(cur->vertex);
}
cur = cur->next;
}
}注意：DFS 用递归实现时，如果图很深，可能会栈溢出。我曾经在一个有 10 万顶点的图上跑递归 DFS，结果程序直接崩了。后来改成用栈模拟，才搞定。
13.4.2 广度优先搜索（BFS）
从一个顶点出发，先访问它所有的邻居，再访问邻居的邻居。像水波一样，一圈一圈往外扩散。
// BFS 队列实现
#include <queue>
void bfs(int start) {
int visited[MAX_V] = {0};
std::queue<int> q;
visited[start] = 1;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
printf("访问顶点: %d\n", u);
Node* cur = adj_list[u];
while (cur) {
if (!visited[cur->vertex]) {
visited[cur->vertex] = 1;
q.push(cur->vertex);
}
cur = cur->next;
}
}
}什么时候用 DFS，什么时候用 BFS？我个人习惯：找路径、拓扑排序用 DFS；求最短路径、层级关系用 BFS。你想想看，BFS 天然就是一层一层走的，求最短路径再合适不过了。
13.5 知识体系总览
下面这张图，把本章的核心知识点串起来了。你看着它，就能回忆起整个图的知识框架。
13.6 避坑指南
我曾经踩过的坑，你千万别再踩：
- 忘记标记已访问：DFS/BFS 遍历时，一定要标记已经访问过的顶点。不然会死循环。我刚开始学的时候，忘了加 visited 数组，结果程序跑起来就停不下来。
- 邻接矩阵的对称性：无向图的邻接矩阵是对称的，添加边时记得加两个方向。有向图则不用。这个搞错了，数据就全乱了。
- 邻接表的内存泄漏：用邻接表时，记得在程序结束前释放所有动态分配的内存。我有一回忘了，跑了几天的大数据任务，内存越占越多，最后服务器直接挂了。
13.7 小结
图这一章，说白了就是三件事：分类（有向/无向）、存储（矩阵/表）、遍历（DFS/BFS）。你把这三点吃透了，后面学最短路径、最小生成树什么的，就轻松多了。
我个人觉得，图是数据结构里最贴近现实世界的东西。社交网络、地图导航、网页链接，背后都是图。你学会了图，就等于掌握了一种描述世界的方式。
嗯，这一章就到这里。代码多写几遍，自然就熟了。