数据结构：图的表示 (Representation of Graphs)

目录

问题的核心——我们要存储什么？

方法一：邻接矩阵 (Adjacency Matrix)

C/C++代码实现（逐步完善）

邻接矩阵的优缺点

方法二：邻接表 (Adjacency List)

C/C++代码实现

邻接表的优缺点

总结与对比

---

上一节，我们从“第一性原理”出发，理解了图（Graph）是一种描述“事物”和“关系”的抽象模型 G = (V, E)。现在，我们要解决一个更实际的问题：如何将这个抽象模型，装进计算机内存里？

这就是 图的表示 (Representation of Graphs)。

数据结构：图（Graph）-CSDN博客

问题的核心——我们要存储什么？

让我们回到图的本质 G = (V, E)。我们要存储的信息无非就是两样：

1. 顶点 (Vertices) 的信息。

2. 边 (Edges) 的信息，也就是顶点之间的关系。

一个好的图表示方法，应该能让我们高效地回答以下两个基本问题：

• 问题一（判断关系）：顶点 u 和顶点 v之间有边吗？

• 问题二（列出关系）：顶点 u 的所有邻居（和它直接相连的顶点）是谁？

带着这两个核心问题，我们来推导最主流的两种表示方法。

---

方法一：邻接矩阵 (Adjacency Matrix)

我们先来思考最直接、最暴力的方法。假设有 N 个顶点，我们可以给它们编号，从 0 到 N-1。

如何表示这 N 个顶点之间的关系呢？

一个很自然的想法就是建立一个“关系表”，就像一张课程表或者棋盘。我们可以用一个二维的方阵（一个 N x N 的表格）来记录所有顶点两两之间的关系。

• 这个表格的行代表“出发”的顶点。

• 这个表格的列代表“到达”的顶点。

• 表格中第 i 行、第 j 列的那个格子，就用来回答“顶点 i 和顶点 j 之间有边吗？”这个问题。

这个 N x N 的“关系表”，就是 邻接矩阵 (Adjacency Matrix)。

一个大小为 N x N 的矩阵 A (其中 N 是顶点的数量)。A[i][j] 的值定义如下：

对于无权图：

A[i][j] = 
{1  如果顶点i和j之间有边0  如果顶点i和j之间没有边
}

对于带权图：

A[i][j] = 
{Wᵢⱼ  如果顶点i和j之间有边，权重为Wᵢⱼ∞    如果没有边（或一个特殊值，如0，取决于权重是否能为0）
}

我们用一个具体的例子来看看邻接矩阵长什么样。

图1️⃣：一个无向无权图

我们先给顶点编号，这非常重要。

    (0) --------- (1)|           / ||          /  ||         /   |(3) --------- (2)

这个图有4个顶点 (V0, V1, V2, V3)，所以我们需要一个 4 x 4 的矩阵。

推导过程：

1. V0相关的边: V0和V1有边，所以 A[0][1] = 1。V0和V3有边，所以 A[0][3] = 1。

2. V1相关的边: V1和V0, V2, V3都有边，所以 A[1][0]=1, A[1][2]=1, A[1][3]=1。

3. ...以此类推，填满整个表格。对于没有边的格子，填0。

最终的邻接矩阵：

      0  1  2  3   <-- 列号 (终点)+------------0 | 0  1  0  11 | 1  0  1  12 | 0  1  0  13 | 1  1  1  0^行号 (起点)

观察这个矩阵，你能发现什么规律吗？

• 对称性：这是一个 对称矩阵（沿左上到右下的对角线对称）。为什么？因为这是个无向图，V0到V1有边，V1到V0必然也有边，所以 A[0][1] 和 A[1][0] 必然相等。

• 对角线：对角线 A[i][i] 全是0。为什么？因为这个图中没有顶点到自身的环（没有自环）。

现在我们来看一个 有向图 的例子。

图2️⃣：一个有向带权图

      (0) ---10---> (1)^             |5 |             | 2|             v(3) <---8---- (2)

推导过程：

1. V0到V1有边，权重10，所以 A[0][1] = 10。

2. V1到V2有边，权重2，所以 A[1][2] = 2。

3. V2到V3有边，权重8，所以 A[2][3] = 8。

4. V3到V0有边，权重5，所以 A[3][0] = 5。

5. 其他没有直接相连的格子，我们用 ∞ (infinity) 表示。

最终的邻接矩阵：

      0     1     2     3+----------------------0 | 0     10    ∞     ∞1 | ∞     0     2     ∞2 | ∞     ∞     0     83 | 5     ∞     ∞     0

观察这个矩阵：它不是对称的！因为 A[0][1]=10，但从V1到V0没有边，所以 A[1][0]=∞。

---

C/C++代码实现（逐步完善）

第一步：定义图的结构

我们需要一个二维数组来存储矩阵，还需要记录顶点的数量。

#include <stdio.h>// 使用宏定义，方便修改图的最大容量
#define MAX_VERTICES 50 
// 定义一个代表无穷大的值，用于带权图。注意要比任何可能的权重都大
#define INFINITY 65535 typedef struct {// 顶点信息可以存在一个单独的数组里，这里为了简化，我们只用 0 到 num_vertices-1 的整数代表顶点int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵int num_vertices; // 顶点的数量int num_edges;    // 边的数量
} AdjMatrixGraph;

这个结构体就是邻接矩阵在代码里的“实体”。

第二步：创建图（初始化）

当我们创建一个图时，需要告诉它有多少个顶点，然后把整个矩阵初始化成一个“没有边”的状态。

// 初始化一个邻接矩阵表示的图
void createGraph(AdjMatrixGraph *g, int num_v) {g->num_vertices = num_v;g->num_edges = 0; // 初始时没有边for (int i = 0; i < g->num_vertices; i++) {for (int j = 0; j < g->num_vertices; j++) {// 对于无权图，初始化为0// 对于带权图，初始化为 INFINITYg->matrix[i][j] = 0; // 我们先按无权图处理}}
}

第三步：添加边

这个操作非常简单，只需要在矩阵的对应位置修改值即可。

// 为无向图添加一条边
void addEdge(AdjMatrixGraph *g, int u, int v) {// 假设 u 和 v 是合法的顶点编号g->matrix[u][v] = 1;g->matrix[v][u] = 1; // 因为是无向图，所以要设置对称位置g->num_edges++;
}

---

邻接矩阵的优缺点

优点 ✅:

1. 判断关系快: 判断顶点 u 和 v 之间是否有边，只需要访问 matrix[u][v]，时间复杂度是 O(1)，非常高效。

2. 实现简单: 基于二维数组，逻辑直观，容易实现。

3. 适用于稠密图 (Dense Graph): 当图中边的数量接近顶点数量的平方时（|E| ≈ |V|^2），空间利用率很高。

缺点 ❌:

1. 空间浪费: 对于 稀疏图 (Sparse Graph)（边的数量远小于顶点数量的平方），矩阵中绝大多数元素都是0或 ∞，造成巨大的空间浪费。比如一个有10000个顶点的图，即使只有几条边，也需要一个 10000 x 10000 的矩阵，这在内存中是难以接受的。

2. 列出关系慢: 要找到顶点 u 的所有邻居，你需要遍历矩阵的第 u 行的所有 N 个元素，时间复杂度是 O(N)（N是顶点数），即使 u 可能只有一个邻居。

---

方法二：邻接表 (Adjacency List)

邻接矩阵最大的问题是为那些 不存在的边 也预留了存储空间。我们能不能换个思路，只存储那些确实存在的边？

这正是邻接表的“第一性原理”。

我们可以这样做：

1. 我们仍然用一个数组，大小为 N，来代表 N 个顶点。

2. 数组的第 i 个位置，不再存储一整行的关系数据，而是只挂一个“列表”。

3. 这个列表里，只记录那些和顶点 i 直接相连的邻居。

这样一来，有多少条边，我们才需要多少存储空间来记录它们。这个“列表”，我们通常用 链表 (Linked List) 来实现，因为它方便动态地添加邻居。

由一个包含 N 个元素的数组构成，数组的第 i 个元素指向一个链表。该链表中的每个节点都代表顶点 i 的一个邻居。

图解时间：我们用回 图1️⃣，看看它的邻接表长什么样。

图1️⃣ (再次登场)

    (0) --------- (1)|           / ||          /  ||         /   |(3) --------- (2)

推导过程：

1. V0: 和它相连的有 V1, V3。所以，在数组第0个位置挂一个链表，链表里包含节点 1 和 3。

2. V1: 和它相连的有 V0, V2, V3。所以，数组第1个位置的链表包含节点 0, 2, 3。

3. ...以此类推。

最终的邻接表：

 顶点数组          链表 (邻居)
+---+
| 0 | ---------> [ 1 ] -> [ 3 ] -> NULL
+---+
| 1 | ---------> [ 0 ] -> [ 2 ] -> [ 3 ] -> NULL
+---+
| 2 | ---------> [ 1 ] -> [ 3 ] -> NULL
+---+
| 3 | ---------> [ 0 ] -> [ 1 ] -> [ 2 ] -> NULL
+---+

• 左边是一个 顶点数组，作为每个链表的头指针入口。

• 右边是多个 链表，每个链表节点存储的是邻居顶点的编号。

• 对于带权图，链表节点里再加一个 weight 成员来存储权重即可。

---

C/C++代码实现

第一步：定义链表节点和顶点节点

我们需要先定义构成链表的节点，它代表一条边。然后定义顶点数组中的元素。

#include <stdio.h>
#include <stdlib.h> // 需要用 malloc// 边节点 (链表节点)
typedef struct EdgeNode {int neighbor_index;     // 邻居顶点在顶点数组中的下标// int weight;          // 如果是带权图，可以在这里加权重struct EdgeNode *next;  // 指向下一个邻居
} EdgeNode;// 顶点节点 (顶点数组中的元素)
typedef struct VertexNode {// char data;            // 顶点本身的数据，比如名字 'A'EdgeNode *first_edge; // 指向该顶点的邻接链表的第一个节点
} VertexNode;

第二步：定义图的结构

图的结构现在是一个 VertexNode 类型的数组。

#define MAX_VERTICES 50typedef struct {VertexNode adj_list[MAX_VERTICES]; // 这就是我们的顶点数组int num_vertices;int num_edges;
} AdjListGraph;

第三步：创建图（初始化）

初始化时，要将所有顶点的 first_edge 指针都设为 NULL，表示它们暂时没有任何邻居。

void createGraph(AdjListGraph *g, int num_v) {g->num_vertices = num_v;g->num_edges = 0;for (int i = 0; i < g->num_vertices; i++) {g->adj_list[i].first_edge = NULL; // 关键一步：初始化为空链表}
}

第四步：添加边

这是邻接表最核心的操作。比如要添加一条边 (u, v)，我们需要：

1. 创建一个新的 EdgeNode 来代表 v。

2. 将这个新节点插入到顶点 u 的邻接链表的头部（头插法最简单，效率是 O(1)）。

3. 如果是无向图，还需要反向操作一次：创建一个代表 u 的节点，插入 v 的链表头部。

// 为无向图添加一条边 (u, v)
void addEdge(AdjListGraph *g, int u, int v) {// ---- 处理 u -> v 的边 ----// 1. 创建新节点EdgeNode *newNode1 = (EdgeNode*)malloc(sizeof(EdgeNode));newNode1->neighbor_index = v;// 2. 头插法插入 u 的链表newNode1->next = g->adj_list[u].first_edge;g->adj_list[u].first_edge = newNode1;// ---- 处理 v -> u 的边 (因为是无向图) ----// 1. 创建新节点EdgeNode *newNode2 = (EdgeNode*)malloc(sizeof(EdgeNode));newNode2->neighbor_index = u;// 2. 头插法插入 v 的链表newNode2->next = g->adj_list[v].first_edge;g->adj_list[v].first_edge = newNode2;g->num_edges++;
}

---

邻接表的优缺点

优点 👍:

1. 空间高效: 对于稀疏图尤其如此。它只为存在的边分配空间。空间复杂度是 O(∣V∣+∣E∣)（∣V∣ 用于顶点数组，|E| 用于链表节点）。

2. 列出关系快: 查找顶点 u 的所有邻居非常方便，只需遍历它的邻接链表即可。时间复杂度与 u 的度数成正比，即 O(textDegree(u))。

缺点 👎:

1. 判断关系慢: 判断顶点 u 和 v 之间是否有边，你需要遍历 u 的整个邻接链表，查看 v 是否在其中。最坏情况下时间复杂度为 O(textDegree(u))，可能高达 O(∣V∣)。

2. 实现稍复杂: 涉及指针和动态内存分配，比纯粹的二维数组要复杂一些。

---

总结与对比

我们来回答最初的两个核心问题，看看这两种表示方法的表现如何：

操作	邻接矩阵 (Adjacency Matrix)	邻接表 (Adjacency List)
空间复杂度	O(V²)	O(V + E)
判断边 (u, v) 是否存在？	O (1) - 极快	O (Degree (u)) - 较慢
列出 u 的所有邻居？	O(V)	O (Degree (u)) - 较快
添加边	O(1)	O(1)

• V 表示顶点数量，E 表示边的数量  

• Degree(u) 表示顶点 u 的度（即与 u 相连的边的数量）  

• 邻接表的空间复杂度是 O(V + E)，因为需要存储所有顶点和边  

• 邻接表列出某个顶点的所有邻居时，只需遍历该顶点对应的链表，时间复杂度与该顶点的度成正比

如何选择？

• 如果你的图是 稠密图（边很多，|E| 接近 |V|^2），或者你需要 频繁地、快速地判断任意两点间是否有边，那么 邻接矩阵 是不错的选择。

• 如果你的图是 稀疏图（边很少，|E| 远小于 |V|^2），并且你更关心 遍历一个顶点的所有邻居，那么 邻接表 是更好的选择。

在现实世界的大多数应用中，图都是稀疏的（比如社交网络，你的好友数远小于全球用户总数），因此 邻接表是迄今为止最常用、最重要的图表示方法。

现在你已经掌握了如何将一个抽象的图结构，用两种主流的方法转化为计算机可以处理的具体数据结构了。这是学习图算法的必备基础！