邻接矩阵存储图实战：C语言实现4种图类型与DFS/BFS遍历（附完整代码）

邻接矩阵存储图实战C语言实现4种图类型与DFS/BFS遍历附完整代码在计算机科学中图是一种非常重要的非线性数据结构广泛应用于社交网络、路径规划、编译器优化等领域。本文将深入探讨如何使用C语言实现一个通用的邻接矩阵图结构支持有向图、无向图、有向网和无向网四种类型并完成深度优先(DFS)和广度优先(BFS)遍历算法。1. 图的基本概念与邻接矩阵存储图(Graph)是由顶点集合和边集合组成的数据结构数学上表示为G(V,E)。根据边是否有方向和权重图可分为四种基本类型有向图(DG): 边有方向无权重有向网(DN): 边有方向有权重无向图(UDG): 边无方向无权重无向网(UDN): 边无方向有权重邻接矩阵是图的一种常见存储方式它使用二维数组表示顶点间的连接关系。对于n个顶点的图邻接矩阵是一个n×n的方阵#define MAX_VERTEX_NUM 20 // 最大顶点数 typedef int VRType; // 顶点关系类型 typedef struct { VRType adj; // 对于无权图用1/0表示是否相邻对于带权图存储权值 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];邻接矩阵的优缺点对比如下存储方式优点缺点邻接矩阵查找任意两顶点关系效率高(O(1))空间复杂度高(O(n²))稀疏图浪费空间邻接表空间利用率高(O(ne))查找特定边效率较低(O(n))2. 图的邻接矩阵实现2.1 图的结构定义我们首先定义图的基本数据结构typedef enum {DG, DN, UDG, UDN} GraphKind; // 图的四种类型 typedef char VertexType[20]; // 顶点类型假设顶点名称不超过20字符 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和边数 GraphKind kind; // 图的种类标志 } MGraph;2.2 图的创建与初始化从文件创建图的函数实现如下void CreateGraphF(MGraph *G) { int i, j, k, w; char filename[13]; VertexType va, vb; FILE *graphlist; scanf(%d, G-kind); // 读取图类型 scanf(%s, filename); // 读取数据文件名 graphlist fopen(filename, r); fscanf(graphlist, %d, G-vexnum); // 顶点数 fscanf(graphlist, %d, G-arcnum); // 边数 // 读取顶点信息 for(i 0; i G-vexnum; i) fscanf(graphlist, %s, G-vexs[i]); // 初始化邻接矩阵 for(i 0; i G-vexnum; i) for(j 0; j G-vexnum; j) G-arcs[i][j].adj (G-kind % 2) ? INFINITY : 0; // 读取边信息并构建邻接矩阵 for(k 0; k G-arcnum; k) { if(G-kind % 2) // 网(有权图) fscanf(graphlist, %s %s %d, va, vb, w); else // 图(无权图) fscanf(graphlist, %s %s, va, vb); i LocateVex(*G, va); j LocateVex(*G, vb); switch(G-kind) { case DG: G-arcs[i][j].adj 1; break; case DN: G-arcs[i][j].adj w; break; case UDG: G-arcs[i][j].adj G-arcs[j][i].adj 1; break; case UDN: G-arcs[i][j].adj G-arcs[j][i].adj w; break; } } fclose(graphlist); }提示LocateVex函数用于查找顶点在顶点数组中的位置索引实现如下int LocateVex(MGraph G, VertexType u) { for(int i 0; i G.vexnum; i) if(strcmp(u, G.vexs[i]) 0) return i; return -1; }3. 图的遍历算法实现3.1 深度优先搜索(DFS)DFS采用递归或栈实现其核心思想是一条路走到黑直到无路可走再回溯。算法步骤如下访问起始顶点v并标记为已访问依次检查v的所有邻接顶点w如果w未被访问则递归调用DFS(w)重复上述过程直到所有顶点都被访问int visited[MAX_VERTEX_NUM]; // 访问标志数组 void DFS(MGraph G, int v) { visited[v] 1; visit(G.vexs[v]); // 访问顶点v for(int w FirstAdjVex(G, G.vexs[v]); w 0; w NextAdjVex(G, G.vexs[v], G.vexs[w])) { if(!visited[w]) DFS(G, w); } } void DFSTraverse(MGraph G) { for(int v 0; v G.vexnum; v) visited[v] 0; for(int v 0; v G.vexnum; v) if(!visited[v]) DFS(G, v); }3.2 广度优先搜索(BFS)BFS采用队列实现其核心思想是层层推进先访问离起始点最近的顶点。算法步骤如下访问起始顶点v并标记为已访问v入队当队列不空时队首顶点u出队依次访问u的所有未访问邻接顶点w标记并入队重复上述过程直到队列为空void BFSTraverse(MGraph G) { int v, u, w; SqQueue Q; for(v 0; v G.vexnum; v) visited[v] 0; InitQueue(Q); for(v 0; v G.vexnum; v) { if(!visited[v]) { visited[v] 1; visit(G.vexs[v]); EnQueue(Q, v); while(!QueueEmpty(Q)) { DeQueue(Q, u); for(w FirstAdjVex(G, G.vexs[u]); w 0; w NextAdjVex(G, G.vexs[u], G.vexs[w])) { if(!visited[w]) { visited[w] 1; visit(G.vexs[w]); EnQueue(Q, w); } } } } } }注意FirstAdjVex和NextAdjVex是获取邻接顶点的辅助函数实现如下int FirstAdjVex(MGraph G, VertexType v) { int k LocateVex(G, v); int j (G.kind % 2) ? INFINITY : 0; for(int i 0; i G.vexnum; i) if(G.arcs[k][i].adj ! j) return i; return -1; } int NextAdjVex(MGraph G, VertexType v, VertexType w) { int k1 LocateVex(G, v); int k2 LocateVex(G, w); int j (G.kind % 2) ? INFINITY : 0; for(int i k2 1; i G.vexnum; i) if(G.arcs[k1][i].adj ! j) return i; return -1; }4. 完整项目实现与测试4.1 项目文件结构graph_project/ ├── main.c # 主程序入口 ├── MGraph.h # 图结构声明 ├── MGraph.c # 图操作实现 ├── sqqueue.h # 队列结构声明 ├── sqqueue.c # 队列操作实现 ├── lt.txt # 测试数据文件1 └── lt2.txt # 测试数据文件24.2 测试数据文件示例lt.txt (无向网测试数据):3 # 图类型(UDN) lt_data.txtlt_data.txt:6 9 # 顶点数 边数 武汉 上海 长沙 北京 成都 广州 # 顶点列表 武汉 长沙 9 武汉 成都 2 长沙 上海 2 长沙 北京 2 上海 北京 5 上海 广州 4 上海 成都 3 北京 广州 8 成都 广州 64.3 主程序示例#include stdio.h #include MGraph.h #include sqqueue.h int main() { MGraph g; CreateGraphF(g); Display(g); printf(深度优先遍历序列:\n); DFSTraverse(g); printf(\n广度优先遍历序列:\n); BFSTraverse(g); return 0; }5. 工程实践中的注意事项在实际项目开发中使用邻接矩阵实现图结构时需要注意以下几点内存优化对于稀疏图邻接矩阵会浪费大量空间可考虑使用邻接表错误处理增加对文件读取、内存分配等操作的错误检查性能考量DFS/BFS的时间复杂度均为O(n²)(邻接矩阵)对于大规模图递归实现的DFS可能导致栈溢出扩展功能添加图的保存功能实现最短路径算法(Dijkstra、Floyd)实现最小生成树算法(Prim、Kruskal)// 示例添加图的保存功能 void SaveGraph(MGraph G, const char* filename) { FILE* fp fopen(filename, w); if(!fp) return; fprintf(fp, %d\n, G.kind); fprintf(fp, %d %d\n, G.vexnum, G.arcnum); for(int i 0; i G.vexnum; i) fprintf(fp, %s , G.vexs[i]); fprintf(fp, \n); for(int i 0; i G.vexnum; i) { for(int j 0; j G.vexnum; j) { if(G.arcs[i][j].adj ! ((G.kind % 2) ? INFINITY : 0)) { fprintf(fp, %s %s, G.vexs[i], G.vexs[j]); if(G.kind % 2) fprintf(fp, %d, G.arcs[i][j].adj); fprintf(fp, \n); } } } fclose(fp); }