数据结构实战：5节点图从邻接矩阵到邻接表的C语言转换与遍历验证

数据结构实战5节点图从邻接矩阵到邻接表的C语言转换与遍历验证在计算机科学中图是一种非常重要的非线性数据结构广泛应用于社交网络、路径规划、编译器设计等领域。图的存储方式主要有邻接矩阵和邻接表两种它们各有优缺点适用于不同的场景。本文将深入探讨这两种存储结构的转换方法并通过广度优先遍历BFS验证转换的正确性。1. 图的存储结构对比1.1 邻接矩阵的特点与实现邻接矩阵是图的最直观表示方法它使用一个二维数组来存储图中顶点之间的连接关系。对于一个包含n个顶点的图邻接矩阵是一个n×n的方阵。#define MAX_VERTEX 5 typedef struct { int matrix[MAX_VERTEX][MAX_VERTEX]; int vertexNum; } AdjMatrixGraph;邻接矩阵的主要特点包括空间复杂度O(n²)适合稠密图查询效率可以在O(1)时间内判断两顶点是否相邻存储方式对于无向图矩阵是对称的对于有向图则不对称1.2 邻接表的特点与实现邻接表是图的另一种常见存储方式它结合了数组和链表为每个顶点维护一个链表存储与该顶点直接相连的其他顶点。typedef struct AdjListNode { int vertex; struct AdjListNode* next; } AdjListNode; typedef struct { AdjListNode* headers[MAX_VERTEX]; int vertexNum; } AdjListGraph;邻接表的主要优势空间效率O(ne)特别适合稀疏图遍历效率可以快速访问某个顶点的所有邻接点扩展性易于添加或删除边1.3 两种存储结构的比较特性邻接矩阵邻接表空间复杂度O(n²)O(ne)查询两顶点连接O(1)O(degree(v))添加边O(1)O(1)删除边O(1)O(degree(v))遍历所有边O(n²)O(ne)适用场景稠密图稀疏图2. 邻接矩阵到邻接表的转换2.1 转换算法设计将邻接矩阵转换为邻接表的核心思想是遍历矩阵的每一行为每个非零元素创建相应的邻接表节点。具体步骤如下初始化邻接表结构遍历邻接矩阵的每一行i对于每一行i遍历每一列j如果matrix[i][j]不为0创建一个新节点并添加到顶点i的链表中重复上述过程直到所有顶点处理完毕2.2 C语言实现代码AdjListGraph* convertMatrixToList(AdjMatrixGraph* matrixGraph) { AdjListGraph* listGraph (AdjListGraph*)malloc(sizeof(AdjListGraph)); listGraph-vertexNum matrixGraph-vertexNum; // 初始化所有头节点 for (int i 0; i matrixGraph-vertexNum; i) { listGraph-headers[i] NULL; } // 转换过程 for (int i 0; i matrixGraph-vertexNum; i) { AdjListNode** current (listGraph-headers[i]); for (int j 0; j matrixGraph-vertexNum; j) { if (matrixGraph-matrix[i][j] ! 0) { AdjListNode* newNode (AdjListNode*)malloc(sizeof(AdjListNode)); newNode-vertex j; newNode-next NULL; *current newNode; current (newNode-next); } } } return listGraph; }2.3 转换过程示例分析假设我们有如下5×5的邻接矩阵表示的图A B C D E A [0,1,0,1,0] B [1,0,1,0,1] C [0,1,0,1,1] D [1,0,1,0,0] E [0,1,1,0,0]转换后的邻接表结构为A - B - D B - A - C - E C - B - D - E D - A - C E - B - C3. 广度优先遍历的实现与验证3.1 BFS算法原理广度优先遍历是一种层次遍历算法它从起始顶点开始先访问所有直接相邻的顶点然后再访问这些相邻顶点的相邻顶点依此类推。BFS通常借助队列来实现访问起始顶点并入队当队列不为空时出队一个顶点访问该顶点的所有未访问邻接顶点并标记为已访问并入队重复上述过程直到队列为空3.2 基于邻接表的BFS实现void BFS(AdjListGraph* graph, int startVertex) { int visited[MAX_VERTEX] {0}; int queue[MAX_VERTEX]; int front 0, rear 0; // 起始顶点入队并标记 queue[rear] startVertex; visited[startVertex] 1; while (front ! rear) { // 出队一个顶点 int current queue[front]; printf(%c , A current); // 遍历所有邻接顶点 AdjListNode* node graph-headers[current]; while (node ! NULL) { int neighbor node-vertex; if (!visited[neighbor]) { visited[neighbor] 1; queue[rear] neighbor; } node node-next; } } printf(\n); }3.3 基于邻接矩阵的BFS实现void matrixBFS(AdjMatrixGraph* graph, int startVertex) { int visited[MAX_VERTEX] {0}; int queue[MAX_VERTEX]; int front 0, rear 0; queue[rear] startVertex; visited[startVertex] 1; while (front ! rear) { int current queue[front]; printf(%c , A current); for (int i 0; i graph-vertexNum; i) { if (graph-matrix[current][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } printf(\n); }3.4 遍历结果验证为了验证转换的正确性我们可以对同一张图分别使用邻接矩阵和邻接表进行BFS遍历比较输出结果是否一致。以顶点E(索引4)为起点两种存储结构的遍历结果应该都是E B C A D4. 完整程序实现与测试4.1 程序框架设计完整的程序应包括以下功能模块邻接矩阵的初始化邻接矩阵到邻接表的转换两种存储结构下的BFS实现结果验证与输出4.2 主程序代码#include stdio.h #include stdlib.h #define MAX_VERTEX 5 // 邻接矩阵结构定义 typedef struct { int matrix[MAX_VERTEX][MAX_VERTEX]; int vertexNum; } AdjMatrixGraph; // 邻接表节点定义 typedef struct AdjListNode { int vertex; struct AdjListNode* next; } AdjListNode; // 邻接表结构定义 typedef struct { AdjListNode* headers[MAX_VERTEX]; int vertexNum; } AdjListGraph; // 初始化邻接矩阵 void initMatrixGraph(AdjMatrixGraph* graph) { int sampleMatrix[MAX_VERTEX][MAX_VERTEX] { {0,1,0,1,0}, {1,0,1,0,1}, {0,1,0,1,1}, {1,0,1,0,0}, {0,1,1,0,0} }; graph-vertexNum MAX_VERTEX; for (int i 0; i MAX_VERTEX; i) { for (int j 0; j MAX_VERTEX; j) { graph-matrix[i][j] sampleMatrix[i][j]; } } } // 邻接矩阵转邻接表 AdjListGraph* convertMatrixToList(AdjMatrixGraph* matrixGraph) { AdjListGraph* listGraph (AdjListGraph*)malloc(sizeof(AdjListGraph)); listGraph-vertexNum matrixGraph-vertexNum; for (int i 0; i matrixGraph-vertexNum; i) { listGraph-headers[i] NULL; AdjListNode** current (listGraph-headers[i]); for (int j 0; j matrixGraph-vertexNum; j) { if (matrixGraph-matrix[i][j] ! 0) { AdjListNode* newNode (AdjListNode*)malloc(sizeof(AdjListNode)); newNode-vertex j; newNode-next NULL; *current newNode; current (newNode-next); } } } return listGraph; } // 打印邻接表 void printAdjList(AdjListGraph* graph) { for (int i 0; i graph-vertexNum; i) { printf(%c: , A i); AdjListNode* node graph-headers[i]; while (node ! NULL) { printf(%c , A node-vertex); node node-next; } printf(\n); } } // 邻接表的BFS实现 void listBFS(AdjListGraph* graph, int startVertex) { printf(邻接表BFS结果: ); // BFS实现代码... } // 邻接矩阵的BFS实现 void matrixBFS(AdjMatrixGraph* graph, int startVertex) { printf(邻接矩阵BFS结果: ); // BFS实现代码... } int main() { AdjMatrixGraph matrixGraph; initMatrixGraph(matrixGraph); AdjListGraph* listGraph convertMatrixToList(matrixGraph); printf(转换后的邻接表:\n); printAdjList(listGraph); printf(\n遍历验证:\n); matrixBFS(matrixGraph, 4); // 从E开始 listBFS(listGraph, 4); // 从E开始 // 释放内存... return 0; }4.3 测试结果分析程序运行后预期输出如下转换后的邻接表: A: B D B: A C E C: B D E D: A C E: B C 遍历验证: 邻接矩阵BFS结果: E B C A D 邻接表BFS结果: E B C A D两种存储结构的遍历结果完全一致验证了转换算法的正确性。在实际应用中开发者可以根据具体场景选择合适的存储结构当需要频繁查询两顶点是否相邻时邻接矩阵更优当处理稀疏图或需要遍历所有边时邻接表更高效5. 性能优化与扩展思考5.1 内存管理优化在邻接表实现中动态内存分配频繁可以考虑以下优化内存池技术预分配一大块内存减少malloc调用次数批量释放维护节点指针数组最后统一释放// 内存池示例 #define MAX_NODES 100 AdjListNode nodePool[MAX_NODES]; int poolIndex 0; AdjListNode* allocNode() { if (poolIndex MAX_NODES) { return nodePool[poolIndex]; } return NULL; }5.2 大规模图处理当图的规模很大时如数百万顶点需要考虑压缩存储使用稀疏矩阵存储技术并行计算利用多线程或GPU加速遍历磁盘存储实现基于磁盘的图算法5.3 其他遍历算法除了BFS图的遍历还有深度优先搜索DFS可以类似实现void DFS(AdjListGraph* graph, int vertex, int* visited) { visited[vertex] 1; printf(%c , A vertex); AdjListNode* node graph-headers[vertex]; while (node ! NULL) { if (!visited[node-vertex]) { DFS(graph, node-vertex, visited); } node node-next; } }5.4 实际应用案例图算法在实际系统中有广泛应用社交网络好友推荐、社区发现路径规划导航系统的最短路径编译器控制流图分析推荐系统用户-商品二分图理解图的存储和遍历原理是掌握这些高级应用的基础。通过本文的实践读者应该能够灵活选择图的存储结构并实现高效的遍历算法。