14. 图的基本概念与存储结构
图，说实话，是数据结构里最灵活、也最让人头疼的一种。树有严格的层次关系，链表有明确的前后指向，但图不一样——它允许任意两个节点之间都有连接。我刚开始学的时候，总觉得图的概念太抽象，直到后来做路由协议的项目，才真正体会到图的威力。
14.1 图的定义与术语
图由两部分组成：顶点集合 V 和边集合 E。记作 G = (V, E)。顶点就是图中的节点，边就是节点之间的连线。
举个例子，一个社交网络里，每个人是一个顶点，好友关系就是一条边。就这么简单。
有向图 vs 无向图
无向图的边没有方向。比如你和同事之间的合作关系，你认识他，他也认识你，这就是无向边。
有向图的边有方向。微博的关注关系就是典型——你关注了大V，大V不一定关注你。这种边用箭头表示，从起点指向终点。
我个人习惯这样记：无向图的边用圆括号 (u, v)，有向图的边用尖括号 <u, v>。写代码的时候，这个区分很重要。
度、入度、出度
无向图中，一个顶点的度就是和它相连的边的数量。有向图就复杂一些：入度是指向该顶点的边数，出度是从该顶点出发的边数。
路径与连通
路径就是从一个顶点到另一个顶点经过的顶点序列。路径的长度是经过的边的数量。
连通这个概念，说白了就是「能不能走过去」。无向图中，任意两个顶点都有路径，就是连通图。有向图里更严格——如果任意两个顶点之间双向都能到达，叫强连通图。
你想想看，地图导航就是典型的连通性问题。两个地点之间有没有路，有几条路，哪条最近——这些都是图论要解决的问题。
14.2 图的邻接矩阵存储
邻接矩阵是最直观的存储方式。用一个 n×n 的二维数组，n 是顶点数。matrix[i][j] = 1 表示顶点 i 到顶点 j 有边，0 表示没有。
无向图的邻接矩阵是对称的，因为 (i, j) 和 (j, i) 是同一条边。有向图就不一定了。
我做过一个项目，顶点数只有几十个，用邻接矩阵非常方便。判断两个顶点是否相连，时间复杂度是 O(1)，直接查数组就行。
#define MAX_VERTEX 100
typedef struct {
int vertex[MAX_VERTEX]; // 顶点数组
int edge[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
int vertexNum, edgeNum; // 顶点数和边数
} MGraph;
// 初始化图
void initGraph(MGraph *G, int n) {
G->vertexNum = n;
G->edgeNum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
G->edge[i][j] = 0;
}
}
}
// 添加无向边
void addUndirectedEdge(MGraph *G, int u, int v) {
G->edge[u][v] = 1;
G->edge[v][u] = 1;
G->edgeNum++;
}14.3 图的邻接表存储
邻接表是另一种思路。每个顶点维护一个链表，链表里存的是和它相连的顶点。这样只存实际存在的边，空间效率高很多。
说白了，邻接表就是「按需分配」。顶点多、边少的情况，邻接表是首选。
#define MAX_VERTEX 100
// 边表节点
typedef struct EdgeNode {
int adjVertex; // 邻接顶点下标
struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;
// 顶点表节点
typedef struct VertexNode {
int data; // 顶点信息
EdgeNode *firstEdge; // 指向第一条边
} VertexNode;
// 图结构
typedef struct {
VertexNode adjList[MAX_VERTEX];
int vertexNum, edgeNum;
} ALGraph;
// 添加有向边
void addDirectedEdge(ALGraph *G, int u, int v) {
EdgeNode *node = (EdgeNode *)malloc(sizeof(EdgeNode));
node->adjVertex = v;
node->next = G->adjList[u].firstEdge;
G->adjList[u].firstEdge = node;
G->edgeNum++;
}注意看，添加边时我用的是头插法。这样新边会插在链表头部，时间复杂度 O(1)。尾插法也可以，但要遍历到链表末尾，效率低一些。
两种存储方式的对比
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(n²) | O(n + e) |
| 判断边是否存在 | O(1) | O(度) |
| 遍历所有边 | O(n²) | O(n + e) |
| 适用场景 | 稠密图 | 稀疏图 |
我个人的经验是：顶点数少于100，且边数接近 n²/2 时，用邻接矩阵。顶点数几百上千，边数远少于 n²，用邻接表。这个选择直接影响程序的内存占用和运行效率。
14.4 知识体系总览
下面这张图把本章的核心内容串起来了。从图的定义出发，分有向和无向两个分支，再到两种存储方式，最后落到实际应用场景。
核心要点：
- 图由顶点和边组成，分有向和无向两大类
- 度、入度、出度是描述顶点连接关系的基本指标
- 连通性决定了图中顶点之间是否能互相到达
- 邻接矩阵适合稠密图，查边快但费内存
- 邻接表适合稀疏图，省内存但查边需要遍历链表
图这块内容，说白了就是两个问题：怎么描述关系，怎么存关系。描述关系靠术语，存关系靠结构。把这两个问题想清楚，后面学图的遍历、最短路径、最小生成树，就会顺很多。
我曾经在做一个网络拓扑分析工具时，一开始用邻接矩阵存了500个节点的图，程序跑起来内存占用直接飙到1MB以上——在嵌入式设备上这简直是灾难。后来改成邻接表，内存降到了200KB左右。所以，选对存储结构，有时候比算法本身更重要。
公众号:蓝海资料掘金营，微信deep3321