ALGraph 邻接表图结构 —— C 语言实现与命名详解
图（Graph）是数据结构中的重要一员，而邻接表（Adjacency List） 是最常用的图存储方式之一。相比邻接矩阵，它在稀疏图场景下更省空间，插入和遍历也更灵活。
本文通过一个完整的 C 语言实现，结合命名拆解和 ASCII 图解，帮助读者彻底搞懂 ALGraph 的设计思路。
整体结构
下图展示了一个 3 顶点 3 条边的无向图在内存中的布局：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| ===================================================================================
[ ALGraph 图的整体结构 ]
===================================================================================
├─ vexnum: 3 (记录当前图有多少个顶点)
├─ arcnum: 3 (记录当前图有多少条边)
├─ kind: 0 (记录图的类型：比如 0 代表无向图)
│
└─ vertices (这是一个 AdjList，本质上就是一个装满 VNode 的大数组)
│
▼
[ VNode 数组 ] [ 链表区域：ArcNode 边节点 ]
┌──────────────┐
0 │ data: 'A' │ (边: 0->1) (边: 0->2)
│ firstarc ────┼───> ┌────────────────┐ ┌────────────────┐
└──────────────┘ │ adjvex: 1 │(指向1) │ adjvex: 2 │(指向2)
│ info: NULL │(无额外信息)│ info: NULL │
│ nextarc ───────┼─────────> │ nextarc: NULL │(链表结束)
└────────────────┘ └────────────────┘
┌──────────────┐
1 │ data: 'B' │ (边: 1->2)
│ firstarc ────┼───> ┌────────────────┐
└──────────────┘ │ adjvex: 2 │(指向2)
│ info: 权重等 │
│ nextarc: NULL │(链表结束)
└────────────────┘
┌──────────────┐
2 │ data: 'C' │ (2号顶点没有向外的连线)
│ firstarc:NULL│───> NULL
└──────────────┘
┌──────────────┐
3 │ (空闲未分配) │
└──────────────┘
... (一直到 MAX_VERTEX_NUM)
|
从图中可以看到：
vertices 是一个固定大小的 VNode 数组，下标对应顶点编号- 每个
VNode 的 firstarc 指针指向一条链表，链表中每个节点（ArcNode）表示一条从该顶点出发的边 - 因为是无向图，边 0⇄1 会同时出现在顶点 0 和顶点 1 的链表里
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100
typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
} ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
} VNode;
typedef VNode AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
int kind;
} ALGraph;
typedef struct {
int data[MAX_VERTEX_NUM];
int front;
int rear;
} Queue;
void addEdge(ALGraph *G, int a, int b)
{
ArcNode *newArc = (ArcNode *)malloc(sizeof(ArcNode));
newArc->adjvex = b;
newArc->nextarc = NULL;
newArc->info = NULL;
if (G->vertices[a].firstarc == NULL) {
G->vertices[a].firstarc = newArc;
} else {
ArcNode *p = G->vertices[a].firstarc;
while (p->nextarc != NULL) p = p->nextarc;
p->nextarc = newArc;
}
}
ALGraph* InitGraph(int n, int m)
{
ALGraph* G = (ALGraph *)malloc(sizeof(ALGraph));
G->vexnum = n;
G->arcnum = m;
G->kind = 0;
for (int i = 0; i < n; i++)
{
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
return G;
}
void DFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (ArcNode *p = G->vertices[v].firstarc; p; p = p->nextarc) {
int i = p->adjvex;
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
void BFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
Queue q;
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
initQueue(&q);
visited[i] = 1;
printf("%d ", i);
enqueue(&q, i);
while (q.front != q.rear) {
int v = dequeue(&q);
for (ArcNode *p = G->vertices[v].firstarc; p; p = p->nextarc) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = 1;
printf("%d ", w);
enqueue(&q, w);
}
}
}
}
}
}
void initQueue(Queue *q)
{
q->front = 0;
q->rear = 0;
}
void enqueue(Queue *q, int x)
{
if ((q->rear + 1) % MAX_VERTEX_NUM == q->front) {
return;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAX_VERTEX_NUM;
}
int dequeue(Queue *q)
{
if (q->front == q->rear) {
return -1;
}
int x = q->data[q->front];
q->front = (q->front + 1) % MAX_VERTEX_NUM;
return x;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
ALGraph* G = InitGraph(n, m);
for (int i = 0; i < m; i++)
{
int a, b;
scanf("%d %d", &a, &b);
addEdge(G, a, b);
addEdge(G, b, a);
}
DFSTraverse(G);
printf("\n");
BFSTraverse(G);
return 0;
}
|
测试与运行示例
输入
含义：3 个顶点（0、1、2），3 条无向边，构成一个完全连通三角形。
输出
1
2
| 0 1 2 ← DFS 深度优先遍历
0 1 2 ← BFS 广度优先遍历
|
结构体与变量命名解析
边的结构体：ArcNode
Arc：英文原意是”弧”。在图论中，有向边通常被称为”弧（Arc）”，无向边被称为”边（Edge）”。在这里统称边的节点。Node：节点。- 变量名拆解：
adjvex = Adjacent + Vex (Vertex的简写)。Adjacent 意思是”邻接的”，Vertex 意思是”顶点”。合起来就是”邻接点”（你要找的那个邻居的下标）。nextarc = Next + Arc。意思是”下一条弧/边”（指向同一个起点的下一条连线）。info = Information。意思是”信息”（用来存距离、路费等边的权重信息）。
顶点的结构体：VNode
V = Vertex（顶点）。Node = 节点。合起来就是”顶点节点”。- 变量名拆解：
data = 数据。这里存的是顶点自己的名字、数据等本体信息。firstarc = First + Arc。意思是”第一条弧/边”（顺着这个指针，就能摸出这个顶点的所有邻居）。
顶点数组（类型别名）：AdjList
Adj = Adjacency（邻接）。List = 表/列表。合起来就是大名鼎鼎的”邻接表”。- 注意：代码里
typedef VNode AdjList[MAX_VERTEX_NUM]; 的意思就是，以后只要我写 AdjList，它就代表一个装满了 VNode 的大数组。
图的总结构体：ALGraph
AL = Adjacency List（邻接表的缩写）。Graph = 图。合起来就是”基于邻接表表示的图”。- (补充：如果是基于邻接矩阵/二维数组表示的图，通常叫
MGraph，M 代表 Matrix 矩阵)
- 变量名拆解：
vertices = Vertex 的复数形式。英语里 vertex 变复数不是加 s，而是变成 vertices。意思是”一堆顶点”。它就是那个存了所有顶点的大数组。vexnum = Vex (Vertex) + Number。顶点的数量。arcnum = Arc + Number。弧/边的数量。kind = 种类。用来标记这是有向图、无向图、网（带权重的图）等。
小节
三个核心单词：
- Vertex（简写 Vex / V）：顶点。
- Arc：弧 / 边。
- Adjacent（简写 Adj）：邻接的。
三个单词拼在一起，就是整个邻接表的核心逻辑了。
