C语言邻接矩阵实战从零实现图的存储与遍历附完整代码在计算机科学中图是一种非常重要的非线性数据结构它由一组顶点和连接这些顶点的边组成。图结构广泛应用于社交网络、路径规划、网络拓扑等众多领域。作为C语言开发者掌握图的存储和遍历技术是解决复杂问题的关键技能之一。邻接矩阵是图最直观的存储方式之一它使用二维数组来表示图中顶点之间的连接关系。这种存储方式虽然在某些情况下会占用较多内存但其实现简单直观特别适合稠密图的存储和快速查询。1. 邻接矩阵的基本原理邻接矩阵的核心思想是用一个二维数组来表示图中顶点之间的连接关系。假设图中有n个顶点那么邻接矩阵就是一个n×n的方阵。对于无权图矩阵中的元素通常这样定义如果顶点i和顶点j之间有边相连则matrix[i][j] 1如果顶点i和顶点j之间没有边相连则matrix[i][j] 0对于带权图网络矩阵中的元素存储的是边的权值通常用一个大数如INT_MAX表示两个顶点之间没有直接连接。邻接矩阵的主要特点无向图的邻接矩阵是对称矩阵可以节省存储空间判断两个顶点是否相邻的时间复杂度为O(1)添加或删除边的时间复杂度也是O(1)空间复杂度为O(n²)对于稀疏图可能造成空间浪费下面是一个简单的无向图及其邻接矩阵表示示例顶点: A, B, C, D 边: A-B, A-C, B-D, C-D 邻接矩阵: A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 02. C语言实现邻接矩阵2.1 数据结构定义首先我们需要定义图的基本数据结构。在C语言中我们可以使用结构体来封装图的顶点信息、邻接矩阵以及相关属性#include stdio.h #include stdlib.h #include limits.h #define MAX_VERTEX 100 // 最大顶点数 #define INFINITY INT_MAX // 表示无穷大(顶点间无直接连接) typedef char VertexType; // 顶点数据类型 typedef struct { VertexType vertices[MAX_VERTEX]; // 顶点数组 int matrix[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵 int vertexCount; // 当前顶点数 int edgeCount; // 当前边数 int isWeighted; // 是否为带权图 int isDirected; // 是否为有向图 } Graph;2.2 图的初始化与顶点添加在创建图之前我们需要初始化邻接矩阵。对于无权图通常将所有元素初始化为0对于带权图则初始化为INFINITY。// 初始化图 void initGraph(Graph *g, int isWeighted, int isDirected) { g-vertexCount 0; g-edgeCount 0; g-isWeighted isWeighted; g-isDirected isDirected; // 初始化邻接矩阵 for (int i 0; i MAX_VERTEX; i) { for (int j 0; j MAX_VERTEX; j) { g-matrix[i][j] isWeighted ? INFINITY : 0; } } } // 添加顶点 int addVertex(Graph *g, VertexType v) { if (g-vertexCount MAX_VERTEX) { printf(顶点数量已达上限!\n); return -1; } g-vertices[g-vertexCount] v; return g-vertexCount; // 返回顶点索引 }2.3 边的添加与查找添加边是图操作中的核心功能。对于有向图和无向图添加边的逻辑略有不同// 查找顶点索引 int findVertexIndex(Graph *g, VertexType v) { for (int i 0; i g-vertexCount; i) { if (g-vertices[i] v) { return i; } } return -1; // 未找到 } // 添加边 void addEdge(Graph *g, VertexType v1, VertexType v2, int weight) { int i findVertexIndex(g, v1); int j findVertexIndex(g, v2); if (i -1 || j -1) { printf(顶点不存在!\n); return; } if (g-isWeighted) { g-matrix[i][j] weight; if (!g-isDirected) { g-matrix[j][i] weight; // 无向图对称 } } else { g-matrix[i][j] 1; if (!g-isDirected) { g-matrix[j][i] 1; } } g-edgeCount; }3. 图的遍历算法实现图的遍历是指从图中某一顶点出发按照某种搜索策略访问图中所有顶点且每个顶点仅被访问一次。常见的遍历方法有深度优先搜索(DFS)和广度优先搜索(BFS)。3.1 深度优先搜索(DFS)深度优先搜索类似于树的先序遍历它沿着图的深度遍历顶点尽可能深地搜索图的分支。当节点v的所有边都已被探索过搜索将回溯到发现节点v的那条边的起始节点。// DFS递归辅助函数 void dfsHelper(Graph *g, int v, int *visited) { visited[v] 1; printf(%c , g-vertices[v]); for (int i 0; i g-vertexCount; i) { int isConnected g-isWeighted ? (g-matrix[v][i] ! INFINITY) : (g-matrix[v][i] 1); if (isConnected !visited[i]) { dfsHelper(g, i, visited); } } } // 深度优先遍历 void dfsTraversal(Graph *g, VertexType start) { int visited[MAX_VERTEX] {0}; int startIndex findVertexIndex(g, start); if (startIndex -1) { printf(起始顶点不存在!\n); return; } printf(深度优先遍历结果: ); dfsHelper(g, startIndex, visited); printf(\n); }3.2 广度优先搜索(BFS)广度优先搜索类似于树的层次遍历它从起始顶点开始先访问起始顶点的所有邻接顶点然后再依次访问这些邻接顶点的邻接顶点。#include stdbool.h // 简单队列实现 typedef struct { int data[MAX_VERTEX]; int front, rear; } Queue; void initQueue(Queue *q) { q-front q-rear 0; } bool isEmpty(Queue *q) { return q-front q-rear; } void enqueue(Queue *q, int v) { q-data[q-rear] v; } int dequeue(Queue *q) { return q-data[q-front]; } // 广度优先遍历 void bfsTraversal(Graph *g, VertexType start) { int visited[MAX_VERTEX] {0}; Queue q; initQueue(q); int startIndex findVertexIndex(g, start); if (startIndex -1) { printf(起始顶点不存在!\n); return; } printf(广度优先遍历结果: ); visited[startIndex] 1; enqueue(q, startIndex); while (!isEmpty(q)) { int v dequeue(q); printf(%c , g-vertices[v]); for (int i 0; i g-vertexCount; i) { int isConnected g-isWeighted ? (g-matrix[v][i] ! INFINITY) : (g-matrix[v][i] 1); if (isConnected !visited[i]) { visited[i] 1; enqueue(q, i); } } } printf(\n); }4. 完整示例与测试现在我们将上述代码整合起来创建一个完整的示例程序演示如何构建图并进行遍历。#include stdio.h #include stdlib.h #include limits.h #include stdbool.h // 此处插入之前定义的所有函数和数据结构 int main() { Graph g; // 创建一个无向无权图 initGraph(g, 0, 0); // 添加顶点 addVertex(g, A); addVertex(g, B); addVertex(g, C); addVertex(g, D); addVertex(g, E); // 添加边 addEdge(g, A, B, 0); addEdge(g, A, C, 0); addEdge(g, B, D, 0); addEdge(g, C, D, 0); addEdge(g, D, E, 0); // 打印邻接矩阵 printf(邻接矩阵:\n); for (int i 0; i g.vertexCount; i) { for (int j 0; j g.vertexCount; j) { printf(%d , g.matrix[i][j]); } printf(\n); } // 遍历测试 dfsTraversal(g, A); bfsTraversal(g, A); // 创建一个有向带权图 Graph weightedGraph; initGraph(weightedGraph, 1, 1); addVertex(weightedGraph, X); addVertex(weightedGraph, Y); addVertex(weightedGraph, Z); addEdge(weightedGraph, X, Y, 5); addEdge(weightedGraph, Y, Z, 3); addEdge(weightedGraph, Z, X, 2); printf(\n带权有向图邻接矩阵:\n); for (int i 0; i weightedGraph.vertexCount; i) { for (int j 0; j weightedGraph.vertexCount; j) { if (weightedGraph.matrix[i][j] INFINITY) { printf(∞ ); } else { printf(%d , weightedGraph.matrix[i][j]); } } printf(\n); } return 0; }程序输出示例邻接矩阵: 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 深度优先遍历结果: A B D C E 广度优先遍历结果: A B C D E 带权有向图邻接矩阵: ∞ 5 ∞ ∞ ∞ 3 2 ∞ ∞5. 性能优化与实用技巧虽然邻接矩阵实现简单但在实际应用中我们还需要考虑一些优化和实用技巧5.1 稀疏图优化对于稀疏图边数远小于顶点数的平方邻接矩阵会浪费大量空间。此时可以考虑以下优化使用邻接表为每个顶点维护一个链表存储其邻接顶点压缩存储对于对称矩阵只存储上三角或下三角部分使用位矩阵对于无权图可以用位运算压缩存储空间5.2 输入处理技巧在交互式程序中处理用户输入时需要注意缓冲区问题。以下是一个健壮的输入处理示例void safeInput(char *prompt, char *format, void *var) { printf(%s, prompt); scanf(format, var); while (getchar() ! \n); // 清空输入缓冲区 } // 使用示例 int main() { Graph g; char v1, v2; int weight; initGraph(g, 1, 0); // 带权无向图 // 添加顶点和边的安全输入 printf(输入顶点数: ); int vertexCount; scanf(%d, vertexCount); while (getchar() ! \n); for (int i 0; i vertexCount; i) { printf(输入第%d个顶点: , i1); char v getchar(); while (getchar() ! \n); addVertex(g, v); } printf(输入边数: ); int edgeCount; scanf(%d, edgeCount); while (getchar() ! \n); for (int i 0; i edgeCount; i) { printf(输入第%d条边(格式: 顶点1 顶点2 权值): , i1); scanf( %c %c %d, v1, v2, weight); while (getchar() ! \n); addEdge(g, v1, v2, weight); } // 其他操作... return 0; }5.3 常见问题排查顶点重复添加在添加顶点前检查是否已存在边重复添加特别是无向图避免重复计数内存管理对于大型图考虑动态内存分配遍历顺序DFS和BFS的结果可能不唯一取决于邻接顶点的处理顺序5.4 扩展功能基于邻接矩阵我们可以实现更多图算法// 检查图是否连通(无向图) int isConnected(Graph *g) { int visited[MAX_VERTEX] {0}; dfsHelper(g, 0, visited); for (int i 0; i g-vertexCount; i) { if (!visited[i]) return 0; } return 1; } // 计算顶点的度(无向图) int vertexDegree(Graph *g, VertexType v) { int index findVertexIndex(g, v); if (index -1) return -1; int degree 0; for (int i 0; i g-vertexCount; i) { if (g-matrix[index][i] ! 0 g-matrix[index][i] ! INFINITY) { degree; } } return degree; }邻接矩阵作为图的基础存储结构虽然简单但功能强大。掌握它的实现原理和应用技巧能为后续学习更复杂的图算法打下坚实基础。在实际项目中根据具体需求选择合适的图存储结构往往能在性能和易用性之间取得良好平衡。