企业官网建设流程全解析

看到这个标题，我第一反应是：这不就是当年数据结构课里那个让我改了半宿 bug 的作业嘛。图的邻接表存储，说难不难，说简单也不简单，很多初学图论的同学都在这里卡过壳：结构体到底该定义几个？边节点怎么挂上去？无向图怎么处理？遍历时 visited 数组放在哪？这些细节单独看都能懂，凑在一起就乱。这篇文章就把一套完整、可编译运行的邻接表代码摆出来，然后用从业者的视角把每个关键决策讲清楚。适合正在学数据结构、准备考研笔试，或者被课程设计折磨的人。如果你已经能手写邻接矩阵，但一直没搞懂邻接表，这篇就是为你准备的。

1. 邻接表到底在解决什么问题

1.1 三种常见图存储方案怎么选

很多人学图的时候，第一个接触的是邻接矩阵。判断两个顶点是否相邻很痛快，A[i][j]一下就知道，但代价是 O(V^2) 的空间。一个 1 万个顶点的图，邻接矩阵要开 1 亿个格子，大部分还是空的，纯属浪费。链式前向星用几条数组模拟链表，省空间且快，但对初学者不友好，理解成本高。邻接表则正好卡在中间：空间只和边数相关，遍历某个顶点的所有邻居也方便，代码写起来也直观。所以教材也好、考试也好，邻接表都是默认必考重点。

这里的 V 是顶点数，E 是边数。实际工程里大多数图都是稀疏的，E 远小于 V^2，所以邻接表是性价比最高的通用选择。

1.2 邻接表的核心设计逻辑

邻接表的本质，是把图拆成两条链：一条是顶点链，另一条是每个顶点下面挂着的邻居链。这就像手机通讯录，每个联系人名字后面挂着一串好友列表；要找某个人有哪些朋友，直接看他的好友列表就行。具体到实现，就是顶点数组每个元素是一个结构体，里面存顶点数据和 firstarc 指针，firstarc 指向第一个邻居节点；每个邻居节点又通过 next 指针串起下一个邻居。这样每个顶点占的空间是固定的，图再大也只是顶点数组变长、链表节点变多。

同一个顶点的所有邻居之间没有顺序要求，所以用头插法还是尾插法都无所谓。头插法每次把新节点插到链表头部，代码短、效率高；尾插法需要从头遍历到尾，或者额外维护一个尾指针。大多数教材代码为了输出顺序和输入顺序一致会用尾插，但实际用邻接表时，邻居顺序不影响算法正确性，所以我在下面的完整代码里统一用头插法。

1.3 邻接表适合哪些场景

如果图是稀疏图，也就是边数远小于 V^2，邻接表明显占优。如果算法需要频繁遍历某顶点的所有出边，比如深度优先搜索、拓扑排序、最短路径里的松弛操作，邻接表天然匹配。反过来，如果经常要判断“A 和 B 之间有没有边”，邻接表就得顺着 A 的链表逐个找，最坏要遍历整个邻居链，此时邻接矩阵更直接。另外，邻接表对动态增删边比较友好，因为链表插入删除都是 O(1) 级别的操作，不涉及移动大量数据。

2. 完整代码：一份能直接跑的C语言实现

2.1 结构体定义为什么是这三板斧

邻接表的结构体就三层：ArcNode 表示一条边，VertexNode 表示一个顶点，ALGraph 包住整个图。ArcNode 里必须有 adjvex，它存的是邻接点在顶点数组中的下标，不是顶点字符本身；weight 存权值，无权图用不上就填 1；next 是链表指针。VertexNode 里 data 存顶点字符，firstarc 存第一条邻接边。ALGraph 里一个固定大小顶点数组和两个计数器，vexnum 和 arcnum。这里的 MAX_VERTEX_NUM 我取了 20，实际使用时可以根据问题规模调大，或者改成动态数组。

为什么要用下标而不是直接用顶点字符？因为字符比较慢，而且图的顶点不一定只有一个字符；用下标作为邻接关系才是标准做法。代码里专门写了 LocateVex 函数，通过字符找下标，这样用户输入仍然方便，内部操作又统一用 int。

2.2 完整代码

下面这份代码保存成adjlist_demo.c，用gcc -std=c99 -o adjlist_demo adjlist_demo.c编译就可以直接运行。它实现了图的创建、邻接表打印、DFS、BFS 和销毁，覆盖了邻接表最常见的所有操作。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; // 邻接点在顶点数组中的下标 int weight; // 边的权值，无权图统一填 1 struct ArcNode *next; // 指向下一条边 } ArcNode; typedef struct VertexNode { char data; // 顶点名字，比如 'A' ArcNode *firstarc; // 第一条依附该顶点的边 } VertexNode; typedef struct { VertexNode vertices[MAX_VERTEX_NUM]; int vexnum; // 当前顶点数 int arcnum; // 当前边数 } ALGraph; // 根据顶点字符返回下标，找不到返回 -1 int LocateVex(ALGraph *G, char v) { for (int i = 0; i < G->vexnum; i++) { if (G->vertices[i].data == v) { return i; } } return -1; } // 初始化：顶点数和边数清零 void InitGraph(ALGraph *G) { G->vexnum = 0; G->arcnum = 0; for (int i = 0; i < MAX_VERTEX_NUM; i++) { G->vertices[i].firstarc = NULL; } } // 插入一条边，默认无向图、带权 void AddEdge(ALGraph *G, char v1, char v2, int weight) { int i = LocateVex(G, v1); int j = LocateVex(G, v2); if (i == -1 || j == -1) { printf("边 (%c, %c) 的顶点不存在，插入失败\n", v1, v2); return; } // 头插法：把 v2 挂到 v1 的链表头 ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; p->weight = weight; p->next = G->vertices[i].firstarc; G->vertices[i].firstarc = p; // 无向图需要再插入一条反向边 ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode)); q->adjvex = i; q->weight = weight; q->next = G->vertices[j].firstarc; G->vertices[j].firstarc = q; G->arcnum++; } // 创建图：由用户输入顶点和边 void CreateGraph(ALGraph *G) { InitGraph(G); int n, m; printf("请输入顶点数和边数："); scanf("%d %d", &n, &m); G->vexnum = n; G->arcnum = 0; printf("请依次输入 %d 个顶点字符：\n", n); for (int i = 0; i < n; i++) { scanf(" %c", &G->vertices[i].data); G->vertices[i].firstarc = NULL; } printf("请依次输入 %d 条边，格式：顶点1 顶点2 权值（无权图权值填 1）：\n", m); for (int k = 0; k < m; k++) { char v1, v2; int w; scanf(" %c %c %d", &v1, &v2, &w); AddEdge(G, v1, v2, w); } } // 打印邻接表 void PrintGraph(ALGraph *G) { printf("\n邻接表如下：\n"); for (int i = 0; i < G->vexnum; i++) { printf("%c(%d)", G->vertices[i].data, i); ArcNode *p = G->vertices[i].firstarc; while (p != NULL) { printf(" -> %c(%d)", G->vertices[p->adjvex].data, p->adjvex); if (p->weight != 1) { printf("[w=%d]", p->weight); } p = p->next; } printf(" -> NULL\n"); } } // 深度优先：从顶点 v 开始递归访问 void DFS(ALGraph *G, int v, bool visited[]) { visited[v] = true; printf("%c ", G->vertices[v].data); ArcNode *p = G->vertices[v].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { DFS(G, p->adjvex, visited); } p = p->next; } } // DFS 入口，处理非连通图 void DFSTraverse(ALGraph *G) { bool visited[MAX_VERTEX_NUM] = {false}; for (int i = 0; i < G->vexnum; i++) { if (!visited[i]) { DFS(G, i, visited); } } printf("\n"); } // 广度优先：数组模拟队列 void BFSTraverse(ALGraph *G) { bool visited[MAX_VERTEX_NUM] = {false}; int queue[MAX_VERTEX_NUM]; int front = 0, rear = 0; for (int i = 0; i < G->vexnum; i++) { if (visited[i]) { continue; } visited[i] = true; printf("%c ", G->vertices[i].data); queue[rear++] = i; while (front < rear) { int v = queue[front++]; ArcNode *p = G->vertices[v].firstarc; while (p != NULL) { int j = p->adjvex; if (!visited[j]) { visited[j] = true; printf("%c ", G->vertices[j].data); queue[rear++] = j; } p = p->next; } } } printf("\n"); } // 释放所有边节点 void DestroyGraph(ALGraph *G) { for (int i = 0; i < G->vexnum; i++) { ArcNode *p = G->vertices[i].firstarc; while (p != NULL) { ArcNode *tmp = p; p = p->next; free(tmp); } G->vertices[i].firstarc = NULL; } G->vexnum = 0; G->arcnum = 0; } int main(void) { ALGraph G; CreateGraph(&G); PrintGraph(&G); printf("DFS 序列："); DFSTraverse(&G); printf("BFS 序列："); BFSTraverse(&G); DestroyGraph(&G); return 0; }

2.3 创建图的核心动作拆解

CreateGraph 的思路是先让用户告诉顶点数和边数，然后依次读入顶点字符，再循环读入每条边的两个端点和权值，每次调用 AddEdge。AddEdge 是重点，它做了三件事：定位两个顶点的下标；创建新节点；头插法挂到链表头部。

为什么用头插而不是尾插？因为头插只要改 firstarc 一个指针，O(1)；尾插需要先找到链表尾，最坏 O(degree)。很多教材为了输出顺序和输入顺序一致会用尾插，代价是多一次遍历，或者多维护一个 tail 指针。我实际写代码时习惯头插，因为省时间，打印出来的邻居顺序和输入顺序相反，这属于正常现象，不是 bug。

无向图要在 AddEdge 里插两次：第一次把 j 插到 i 的链表，第二次把 i 插到 j 的链表。如果做有向图，把第二次插入删掉即可。带权图把 weight 存进去；不带权图统一赋 1。全代码为了兼容带权，接口统一为“顶点1 顶点2 权值”。

另外注意输入格式细节：scanf(" %c %c %d", &v1, &v2, &w);里的%c前面加空格，是为了吞掉上一次输入残留在缓冲区里的换行或空格。新手最容易在这里翻车，后面专门说。

3. 遍历实现：DFS与BFS在邻接表上的正确姿势

3.1 深度优先：递归加一个visited数组

图遍历和树遍历最大的不同是图有环，所以必须有一个 visited 数组记录哪些顶点已经访问过。DFS 从某个顶点进去，先标记再打印，然后依次递归访问它的每个邻居；如果邻居已经访问过就跳过。这里我在 DFSTraverse 外层套了一个 for 循环，把非连通图也覆盖了：如果遍历完一个连通分量还有没访问的顶点，就再从新的起点开始。这是很多初学版本容易漏的地方。

递归实现代码短，但图特别大时递归层数可能等于顶点数，有爆栈风险。如果题目要求极大规模，可以改成显式栈的迭代版；课程设计和考试用递归已经够用。实际调试时，我最常犯的错是忘记把 visited 数组初始化，或者初始化成{true}，导致图里很多顶点没被访问到。一定要用{false}或显式 memset。

3.2 广度优先：数组模拟队列避免依赖

BFS 的核心是队列。这里我用数组模拟了一个最简单的队列，front 和 rear 分别是队头和队尾。为了不引入额外的 queue 库，数组容量直接定为 MAX_VERTEX_NUM，因为每个顶点最多入队一次，队列长度不会超过顶点数。外层 for 循环同样是为了处理非连通图。

BFS 的经典错误是出队时才标记 visited，这会导致同一个节点被多次入队。正确做法是在入队那一刻就把 visited 置为 true，因为只要它已经在队列里，就不需要再放一次了。我见过不少同学写的 BFS，队列里反复出现同一个顶点，图复杂一点就直接死循环，排查半天才发现是标记时机问题。

3.3 复杂度分析：O(V+E)是怎么算出来的

邻接表遍历的时间复杂度，直观上就是每个顶点被访问一次，每条边被扫描一次。无向图中每条边存了两份，所以总共要过 2E 个边节点；有向图过 E 个；加上顶点上的 O(V)，最终 O(V+E)。邻接矩阵则是 O(V^2)，因为不管图多稀疏，都要把矩阵扫一遍。空间上，邻接表存 V 个顶点头节点加 2E（无向）或 E（有向）个边节点，是 O(V+E)。

这也是为什么大部分图算法都偏爱邻接表：在稀疏图里，O(V+E) 和 O(V^2) 之间差了一个量级。如果题目给的是 10 万顶点、20 万边，邻接矩阵根本开不出来，邻接表却轻轻松松。

4. 踩坑记录：邻接表代码里的高频错误

4.1 头插法写成了尾插法，链表顺序错乱但没崩

头插法核心就三句话：新节点的 next 指向原来的 firstarc，然后 firstarc 指向新节点。顺序写反就变成自环或者丢链表。我见过某同学把p->next = G->vertices[i].firstarc漏了，结果每个顶点的链表只有最后一个插入的边，前面的边全都丢了。调试时打印邻接表，发现边数对不上，才意识到是头插顺序错了。

写头插法的时候，最好在纸上画一下两个节点是怎么勾上的：新节点先指旧头，再把头指针挪到新节点。这个顺序不能反。如果反了，旧链表就断了，而且没有任何编译器报错，属于典型的逻辑错误。

4.2 无向图只插入了一条边

这个错误非常隐蔽。有些同学的 AddEdge 只写了一次插入，然后以为输入一条边就完了。对于无向图，A 到 B 有边，意味着 B 到 A 也有边，所以 B 的链表里必须也有 A。否则遍历到 B 的时候，发现 B 没有邻居，整个图的连通性都是错的。

判断自己有没有犯这个错，最直接的办法是打印邻接表后，检查每条无向边是否在两个顶点里都出现了。如果只出现了一次，要么是代码只插一次，要么是 AddEdge 里第二次插入用的变量写错了。

4.3 忘了销毁链表，内存泄漏在课设里看不见

小图跑一次，进程结束内存自动回收，看不出问题。但如果写的是服务程序，或者同一个函数里反复创建图，不销毁链表就会造成内存泄漏。我在代码里专门写了 DestroyGraph，释放每个顶点的整条链表，然后把 firstarc 置空。这是很多教材代码不写、但真正工程里必须有的操作。

如果你用内存检测工具跑一下，比如 Valgrind，就能看到有多少字节的块被 leaked。养成写完销毁函数的习惯，不仅课设能加分，以后写 C/C++ 也会少很多麻烦。

4.4 顶点编号从0还是从1开始，下标串位

很多图论题喜欢用 1 到 N 作为顶点编号，但 C 语言数组下标从 0 开始。如果 LocateVex 返回的 i 直接拿来当数组下标，而用户输入的是“1, 2, 3”，那顶点 1 会存到下标 0，顶点 N 会存到下标 N-1，看起来没问题，但涉及边的时候很容易下标越界。

稳妥的做法是不要依赖顶点字符等于数组下标，所有访问都通过 LocateVex 转换。这样即便用户输入了任意字符或编号，代码都能正确索引。如果顶点很多，LocateVex 的线性查找是 O(V)，对创建过程可以接受；如果追求性能，可以换哈希表或者建一个字符到下标的映射。

4.5 输入缓冲区问题：scanf("%c")吃空格和换行

scanf("%c")不会跳过空白字符，这是 C 语言的一个大坑。如果代码里写scanf("%c", &v1)，前面输入完整数后的换行会被当成一个合法字符读进去，导致 v1 读到\n，程序直接莫名其妙结束。解决方案很简单：所有读取单个字符的 scanf 格式串里，%c前面加一个空格，写成" %c"。

我在完整代码里已经这么处理了。但如果你抄了网上的旧代码，里面没有加空格，运行时就很容易在输入边那里卡住。这也是邻接表题目里最常见的“运行时错误”来源之一。

5. 不只是作业：邻接表的变体和工程扩展

5.1 逆邻接表、十字链表、邻接多重表

邻接表适合求某顶点的出边，但要求入边时效率不高。于是就有了逆邻接表：每个顶点挂的是“谁指向我”的链表。对有向图，如果既要出边又要入边，可以把邻接表和逆邻接表合起来，这就是十字链表。对于无向图，每条边在两个链表里各存一次，维护起来有点冗余，又演化出了邻接多重表，用一条边节点同时挂到两个顶点的链里。

这些变体本质上都是“数组 + 链表”的排列组合。把基础邻接表的指针关系搞明白，再看这些变体就很轻松。

5.2 用C++/Python实现邻接表，写起来能快多少

如果考试手写，C 语言是最稳的。如果做工程或者刷 LeetCode，用高级语言会省很多事。C++ 里可以直接用vector<list<pair<int,int>>>，甚至vector<vector<pair<int,int>>>更常见。Python 则可以用字典，key 是顶点，value 是邻居列表：

graph = { 'A': [('B', 1), ('C', 1)], 'B': [('A', 1), ('C', 1)], 'C': [('A', 1), ('B', 1)] }

这种写法的好处是框架帮你处理了内存和扩容，但底层思想还是邻接表。如果只是在本地跑小数据，高级语言确实香；可一旦要理解指针和内存布局，还是得回到 C 语言这一版。

5.3 邻接表在后边的图算法里是怎么“打工”的

很多算法都是在邻接表基础上跑的。比如拓扑排序，需要先统计每个顶点的入度，入度正好可以用一个数组保存，然后从入度为 0 的顶点开始，每访问一个顶点就把它的所有邻居入度减一，这时候遍历邻居链表就非常自然。再比如 Dijkstra 求最短路径，每次从堆里弹出当前距离最小的顶点，然后遍历它的邻接表去松弛邻居，这一步就是整个算法的核心循环。

如果你打算把数据结构这条路走深一点，邻接表不是一个孤立的模板题，它是后面所有图算法的基础设施。把创建、遍历、销毁这套基本功练熟，后面写拓扑排序、最短路径、最小生成树都会顺手很多。

最后分享一个我自己调图代码的习惯：每写完 AddEdge，就立刻调用一次 PrintGraph，确认刚插入的边在两个顶点的链表里都存在。这个习惯帮我少调了很多次 bug。如果只是应付笔试，手写结构体和头插法足够了；但真要上机或者做课设，内存释放和输入解析才是隐藏的扣分点，别觉得小，踩一次就知道疼。