数据结构图论实战邻接矩阵与邻接表C语言实现6种算法完整代码解析1. 图的存储结构设计与实现在计算机科学中图是一种非常重要的非线性数据结构它由顶点集合和边集合组成。图的存储结构直接影响算法的效率和实现复杂度邻接矩阵和邻接表是两种最常用的存储方式。1.1 邻接矩阵实现邻接矩阵使用二维数组来表示图中顶点之间的连接关系。对于有n个顶点的图邻接矩阵是一个n×n的方阵。#define MAX_VERTEX 100 // 最大顶点数 typedef char VertexType; // 顶点数据类型 typedef int EdgeType; // 边权值类型 typedef struct { VertexType vexs[MAX_VERTEX]; // 顶点集合 EdgeType edges[MAX_VERTEX][MAX_VERTEX]; // 边集合 int vertexNum, edgeNum; // 顶点数和边数 int graphType; // 0-无向图 1-有向图 } MGraph;邻接矩阵的初始化函数如下void InitMGraph(MGraph *G, int type) { G-vertexNum 0; G-edgeNum 0; G-graphType type; for(int i0; iMAX_VERTEX; i) { for(int j0; jMAX_VERTEX; j) { if(i j) G-edges[i][j] 0; // 对角线设为0 else G-edges[i][j] INT_MAX; // 初始化为无穷大 } } }邻接矩阵的特点空间复杂度O(V²)V为顶点数适用场景稠密图边数接近顶点数平方优势快速判断两顶点间是否有边O(1)方便计算顶点的度无向图或出度有向图1.2 邻接表实现邻接表使用数组加链表的方式存储图数组部分存储顶点信息链表存储邻接顶点。typedef struct EdgeNode { // 边表结点 int adjvex; // 邻接点索引 EdgeType weight; // 边权值 struct EdgeNode *next; // 指向下一个邻接点 } EdgeNode; typedef struct VertexNode { // 顶点表结点 VertexType data; // 顶点数据 EdgeNode *firstEdge; // 边表头指针 int inDegree; // 顶点入度拓扑排序用 } VertexNode; typedef struct { VertexNode adjList[MAX_VERTEX]; int vertexNum, edgeNum; int graphType; } ALGraph;邻接表的初始化函数void InitALGraph(ALGraph *G, int type) { G-vertexNum 0; G-edgeNum 0; G-graphType type; for(int i0; iMAX_VERTEX; i) { G-adjList[i].firstEdge NULL; G-adjList[i].inDegree 0; } }邻接表的特点空间复杂度O(VE)V为顶点数E为边数适用场景稀疏图边数远小于顶点数平方优势节省存储空间方便找到任一顶点的所有邻接点1.3 存储结构对比特性邻接矩阵邻接表空间复杂度O(V²)O(VE)查询边是否存在O(1)O(degree(V))遍历所有邻接点O(V)O(degree(V))添加边O(1)O(1)或O(logV)删除边O(1)O(degree(V))适用场景稠密图稀疏图提示在实际应用中应根据图的特点和算法需求选择合适的存储结构。稠密图或需要频繁查询边存在性的场景适合邻接矩阵而稀疏图或需要频繁遍历邻接点的场景适合邻接表。2. 图的遍历算法实现图的遍历是图算法的基础深度优先搜索(DFS)和广度优先搜索(BFS)是两种最基本的遍历方法。2.1 深度优先搜索(DFS)DFS采用递归或栈的方式实现尽可能深地搜索图的分支。邻接矩阵DFS实现int visited[MAX_VERTEX] {0}; // 访问标记数组 void DFS_M(MGraph G, int v) { visited[v] 1; printf(%c , G.vexs[v]); for(int i0; iG.vertexNum; i) { if(G.edges[v][i] ! 0 G.edges[v][i] ! INT_MAX !visited[i]) { DFS_M(G, i); } } }邻接表DFS实现void DFS_AL(ALGraph G, int v) { visited[v] 1; printf(%c , G.adjList[v].data); EdgeNode *p G.adjList[v].firstEdge; while(p ! NULL) { if(!visited[p-adjvex]) { DFS_AL(G, p-adjvex); } p p-next; } }2.2 广度优先搜索(BFS)BFS采用队列的方式实现逐层遍历图的顶点。邻接矩阵BFS实现void BFS_M(MGraph G, int v) { int queue[MAX_VERTEX], front0, rear0; printf(%c , G.vexs[v]); visited[v] 1; queue[rear] v; while(front ! rear) { int w queue[front]; for(int i0; iG.vertexNum; i) { if(G.edges[w][i] ! 0 G.edges[w][i] ! INT_MAX !visited[i]) { printf(%c , G.vexs[i]); visited[i] 1; queue[rear] i; } } } }邻接表BFS实现void BFS_AL(ALGraph G, int v) { int queue[MAX_VERTEX], front0, rear0; printf(%c , G.adjList[v].data); visited[v] 1; queue[rear] v; while(front ! rear) { int w queue[front]; EdgeNode *p G.adjList[w].firstEdge; while(p ! NULL) { if(!visited[p-adjvex]) { printf(%c , G.adjList[p-adjvex].data); visited[p-adjvex] 1; queue[rear] p-adjvex; } p p-next; } } }2.3 遍历算法对比特性DFSBFS数据结构栈递归队列空间复杂度O(h) h为树高O(w) w为树宽适用场景寻找所有解、拓扑排序最短路径、连通分量邻接点访问顺序深度优先广度优先注意对于非连通图需要检查所有顶点是否被访问过对未访问顶点再次调用遍历函数。3. 拓扑排序算法实现拓扑排序是针对有向无环图(DAG)的线性排序使得对于图中的每一条有向边(u,v)u在排序中总是位于v的前面。3.1 基于邻接表的拓扑排序int TopologicalSort(ALGraph G) { int stack[MAX_VERTEX], top -1; int count 0; // 输出顶点计数器 // 将入度为0的顶点入栈 for(int i0; iG.vertexNum; i) { if(G.adjList[i].inDegree 0) { stack[top] i; } } while(top ! -1) { int v stack[top--]; printf(%c , G.adjList[v].data); count; // 删除以v为起点的边 EdgeNode *p G.adjList[v].firstEdge; while(p ! NULL) { int w p-adjvex; G.adjList[w].inDegree--; if(G.adjList[w].inDegree 0) { stack[top] w; } p p-next; } } if(count G.vertexNum) { printf(\n图中存在环无法完成拓扑排序\n); return 0; } return 1; }3.2 拓扑排序的应用场景任务调度确定任务的执行顺序保证前置任务先完成课程选修确定课程的学习顺序先修课程在前依赖解析如软件包安装依赖关系编译顺序源文件编译的顺序依赖提示拓扑排序的结果不唯一一个DAG可能有多个有效的拓扑排序序列。算法的时间复杂度为O(VE)其中V是顶点数E是边数。4. 最小生成树算法最小生成树(Minimum Spanning Tree, MST)是在一个带权无向图中找到一棵生成树使得所有边的权值之和最小。Prim和Kruskal是两种经典算法。4.1 Prim算法实现Prim算法从某个顶点开始逐步扩展生成树每次选择连接生成树和非生成树顶点中权值最小的边。void Prim(MGraph G) { EdgeType lowcost[MAX_VERTEX]; // 生成树到各顶点的最小权值 int adjvex[MAX_VERTEX]; // 最小权值对应的顶点 int min, j, k; // 初始化从顶点0开始 for(int i1; iG.vertexNum; i) { lowcost[i] G.edges[0][i]; adjvex[i] 0; } lowcost[0] 0; // 表示顶点0已加入生成树 for(int i1; iG.vertexNum; i) { min INT_MAX; j 1; k 0; // 找出当前lowcost中的最小值 while(j G.vertexNum) { if(lowcost[j] ! 0 lowcost[j] min) { min lowcost[j]; k j; } j; } printf((%c,%c) , G.vexs[adjvex[k]], G.vexs[k]); lowcost[k] 0; // 标记顶点k已加入生成树 // 更新lowcost数组 for(j1; jG.vertexNum; j) { if(lowcost[j] ! 0 G.edges[k][j] lowcost[j]) { lowcost[j] G.edges[k][j]; adjvex[j] k; } } } }4.2 Kruskal算法实现Kruskal算法按权值从小到大选择边如果该边不会形成环则加入生成树。typedef struct { int begin; int end; EdgeType weight; } Edge; // 边结构体 int Find(int *parent, int f) { while(parent[f] 0) { f parent[f]; } return f; } void Kruskal(MGraph G) { Edge edges[MAX_VERTEX*MAX_VERTEX]; int parent[MAX_VERTEX]; int k 0; // 将边集存入edges数组 for(int i0; iG.vertexNum; i) { for(int ji1; jG.vertexNum; j) { if(G.edges[i][j] ! INT_MAX) { edges[k].begin i; edges[k].end j; edges[k].weight G.edges[i][j]; k; } } } // 按权值从小到大排序 for(int i0; iG.edgeNum-1; i) { for(int ji1; jG.edgeNum; j) { if(edges[i].weight edges[j].weight) { Edge temp edges[i]; edges[i] edges[j]; edges[j] temp; } } } for(int i0; iG.vertexNum; i) { parent[i] 0; } for(int i0; iG.edgeNum; i) { int n Find(parent, edges[i].begin); int m Find(parent, edges[i].end); if(n ! m) { // 不构成环 parent[n] m; printf((%c,%c) , G.vexs[edges[i].begin], G.vexs[edges[i].end]); } } }4.3 最小生成树算法对比特性Prim算法Kruskal算法时间复杂度O(V²)邻接矩阵O(ElogE)排序主导适用存储结构邻接矩阵/邻接表边集数组适用场景稠密图稀疏图算法思想顶点扩展边选择注意Prim算法适合边稠密的图Kruskal算法适合边稀疏的图。在实际应用中可以使用优先队列(堆)来优化Prim算法使其时间复杂度降为O(ElogV)。5. 最短路径算法最短路径算法用于在带权图中找到两个顶点之间的最短路径Dijkstra算法是解决单源最短路径问题的经典算法。5.1 Dijkstra算法实现Dijkstra算法采用贪心策略逐步确定从源点到其他各顶点的最短路径。void Dijkstra(MGraph G, int v0) { int dist[MAX_VERTEX]; // 最短路径长度 int path[MAX_VERTEX]; // 前驱顶点 int final[MAX_VERTEX] {0}; // 是否已找到最短路径 // 初始化 for(int i0; iG.vertexNum; i) { dist[i] G.edges[v0][i]; path[i] (G.edges[v0][i] INT_MAX) ? v0 : -1; } dist[v0] 0; final[v0] 1; for(int i1; iG.vertexNum; i) { int min INT_MAX; int k 0; // 找出当前dist中的最小值 for(int j0; jG.vertexNum; j) { if(!final[j] dist[j] min) { min dist[j]; k j; } } final[k] 1; // 更新dist和path数组 for(int j0; jG.vertexNum; j) { if(!final[j] (min G.edges[k][j] dist[j])) { dist[j] min G.edges[k][j]; path[j] k; } } } // 输出最短路径 for(int i0; iG.vertexNum; i) { if(i ! v0) { printf(\n%c到%c的最短路径长度为%d\n, G.vexs[v0], G.vexs[i], dist[i]); printf(路径为%c, G.vexs[i]); int j i; while(path[j] ! v0) { printf(-%c, G.vexs[path[j]]); j path[j]; } printf(-%c, G.vexs[v0]); } } }5.2 最短路径算法应用场景路由选择网络数据包传输路径选择交通导航地图应用中寻找最短行车路线任务调度确定关键路径和任务优先级网络分析社交网络中分析人际关系距离提示Dijkstra算法不能处理带有负权边的图。对于包含负权边的图可以使用Bellman-Ford算法。如果需要计算所有顶点对之间的最短路径可以使用Floyd算法其时间复杂度为O(V³)。6. 算法性能对比与工程实践6.1 算法时间复杂度对比算法邻接矩阵邻接表DFS/BFSO(V²)O(VE)拓扑排序O(V²)O(VE)PrimO(V²)O(ElogV)KruskalO(ElogE)O(ElogE)DijkstraO(V²)O(ElogV)6.2 工程实践建议存储结构选择对于稠密图或需要频繁查询边存在性的场景优先选择邻接矩阵对于稀疏图或需要频繁遍历邻接点的场景优先选择邻接表算法选择最小生成树稠密图用Prim稀疏图用Kruskal最短路径单源无负权边用Dijkstra有负权边用Bellman-Ford全源最短路径用Floyd性能优化使用优先队列(堆)优化Prim和Dijkstra算法对于大规模图考虑使用并行算法或分布式计算框架内存管理邻接表的边节点使用内存池技术减少内存碎片对于固定大小的图可以使用静态数组代替动态分配代码可读性将图结构和算法分离提高代码复用性使用清晰的命名和注释特别是对于复杂的图算法// 示例优化的邻接表结构设计 typedef struct { VertexType data; EdgeNode *firstEdge; int inDegree; // 添加其他必要字段如距离估计、颜色标记等 int distance; // 用于最短路径算法 int color; // 用于遍历算法标记 } AdvancedVertexNode;在实际项目中图算法的实现往往需要根据具体需求进行调整和优化。例如在路由算法中可能需要结合启发式方法在社交网络分析中可能需要考虑动态图的处理。理解这些基础算法的原理和实现方式是解决更复杂图论问题的基础。
