无向图邻接矩阵实现与遍历实战：从理论到C语言代码解析-智慧文博士

1. 无向图与邻接矩阵基础

第一次接触图结构时，我盯着那些密密麻麻的线条和数字看了半天。后来才发现，无向图其实就是用圆圈（顶点）和连线（边）组成的结构，就像地铁线路图那样简单。比如北京地铁4号线和10号线在海淀黄庄站相交，这两个站点就是顶点，线路就是边。

邻接矩阵则是把这种关系转换成二维表格的存储方式。假设我们有4个地铁站（A、B、C、D），用矩阵表示就是：

A B C D A [0 1 1 0] B [1 0 1 1] C [1 1 0 0] D [0 1 0 0]

这里的1表示两站连通（比如A-B有连线），0表示不连通。因为是无向图，矩阵总是对称的——A到B和B到A是同一件事。

实际项目中我遇到过内存浪费的问题。当有1000个站点但只有2000条线路时，矩阵里98%的空间都是0。这时候用邻接表更划算，但邻接矩阵在查找两个站点是否直达时更快，直接查表就行。

2. C语言实现邻接矩阵

先看核心数据结构设计。我习惯用结构体封装，这样代码更清晰：

#define MAX_SIZE 100 // 最大顶点数 typedef struct { int nodes[MAX_SIZE]; // 顶点集合 int edges[MAX_SIZE][MAX_SIZE]; // 邻接矩阵 int nodeCount; // 顶点数 int edgeCount; // 边数 } Graph;

初始化矩阵时有个坑要注意：必须显式把所有边初始化为0。有次我忘记初始化，遍历时出现了随机值导致程序崩溃：

void initGraph(Graph *g, int n) { g->nodeCount = n; g->edgeCount = 0; memset(g->edges, 0, sizeof(g->edges)); // 关键步骤！ }

添加边的函数需要处理无向图的对称性。比如添加边A-B：

void addEdge(Graph *g, int v1, int v2) { if (v1 == v2) return; // 防止自环 g->edges[v1][v2] = 1; g->edges[v2][v1] = 1; // 无向图要设置对称位置 g->edgeCount++; }

测试时可以打印矩阵验证：

void printMatrix(Graph *g) { for (int i = 0; i < g->nodeCount; i++) { for (int j = 0; j < g->nodeCount; j++) { printf("%d ", g->edges[i][j]); } printf("\n"); } }

3. 深度优先遍历（DFS）实战

DFS就像走迷宫时右手扶墙策略。从起点出发，沿着一条路走到尽头，然后回退到最近的分叉点。用递归实现最直观：

int visited[MAX_SIZE]; // 访问标记数组 void dfs(Graph *g, int v) { visited[v] = 1; printf("%d ", g->nodes[v]); // 访问当前顶点 for (int i = 0; i < g->nodeCount; i++) { if (g->edges[v][i] && !visited[i]) { dfs(g, i); // 递归访问邻接点 } } }

非递归版本需要用栈模拟。我更喜欢用数组实现栈，比链表更省内存：

void dfsNonRecursive(Graph *g, int start) { int stack[MAX_SIZE], top = -1; memset(visited, 0, sizeof(visited)); stack[++top] = start; visited[start] = 1; while (top != -1) { int v = stack[top--]; printf("%d ", g->nodes[v]); for (int i = g->nodeCount-1; i >= 0; i--) { if (g->edges[v][i] && !visited[i]) { visited[i] = 1; stack[++top] = i; } } } }

注意邻接点要逆序入栈，这样才能保持与递归相同的访问顺序。

4. 广度优先遍历（BFS）精解

BFS就像水面波纹扩散，一层层向外探索。必须用队列实现，C语言中可以用数组模拟循环队列：

#define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front, rear; } Queue; void bfs(Graph *g, int start) { Queue q = { .front = 0, .rear = 0 }; memset(visited, 0, sizeof(visited)); q.data[q.rear++] = start; visited[start] = 1; while (q.front != q.rear) { int v = q.data[q.front++]; printf("%d ", g->nodes[v]); for (int i = 0; i < g->nodeCount; i++) { if (g->edges[v][i] && !visited[i]) { visited[i] = 1; q.data[q.rear++] = i; } } } }

在社交网络分析中，BFS可以用来查找三度人脉。我曾用这个算法实现了"可能认识的人"推荐功能。

5. 完整应用案例

结合地铁换乘查询的实例。先构建图：

Graph g; initGraph(&g, 6); // 6个站点 addEdge(&g, 0, 1); // A-B addEdge(&g, 0, 2); // A-C addEdge(&g, 1, 3); // B-D addEdge(&g, 2, 3); // C-D addEdge(&g, 3, 4); // D-E addEdge(&g, 4, 5); // E-F

DFS和BFS的遍历结果会不同：

DFS: A B D C E F BFS: A B C D E F

实际调试时遇到过队列溢出问题。当站点超过100时，需要动态调整队列大小或改用链表队列。

6. 性能优化技巧

空间优化：对于稀疏图，可以用位压缩。比如用1个int表示32个边状态，空间减少32倍。

时间优化：并行化BFS。在多层遍历时，可以同时处理当前层的所有邻接点。用OpenMP实现：

#pragma omp parallel for for (int i = 0; i < g->nodeCount; i++) { if (g->edges[v][i] && !visited[i]) { #pragma omp critical { visited[i] = 1; q.data[q.rear++] = i; } } }

算法选择：在路径规划中，DFS适合找所有可能路线，BFS适合找最短路径。我曾用DFS生成迷宫所有解法，用BFS实现最短逃生路径计算。

最后提醒：遍历时要记得重置visited数组。有次我在连续调用时没清空，导致第二次遍历直接跳过所有节点，排查了半天才发现这个问题。