图论基础：数据结构与算法中的图存储与遍历

1. 数据结构与算法中的图论基础图论作为离散数学的重要分支在计算机科学领域有着广泛的应用。山东理工大学SDUT的数据结构与算法课程中图论部分主要涵盖图的存储结构、遍历算法以及典型应用场景。这部分内容在PTA程序设计类实验辅助教学平台的题目中体现为对邻接矩阵、邻接表等存储结构的实现以及深度优先搜索DFS、广度优先搜索BFS等算法的应用。图的数学定义为一个二元组G(V,E)其中V是顶点的有限集合E是边的集合。根据边是否有方向可分为有向图和无向图根据边是否带有权值可分为带权图和无权图。在实际编程题目中我们需要根据问题特点选择合适的表示方法。1.1 图的存储结构实现邻接矩阵是图最常见的存储方式之一特别适用于稠密图。对于一个有n个顶点的图可以用n×n的二维数组表示。矩阵中的值可以表示边的存在与否0/1或边的权值。这种方式的优点是查询两点间边的存在性非常高效O(1)时间复杂度但空间复杂度为O(n²)对于稀疏图会造成空间浪费。#define MAX_VERTEX_NUM 100 // 最大顶点数 typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点表 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertexNum, edgeNum; // 当前顶点数和边数 } MGraph;邻接表则更适合存储稀疏图它结合了顺序存储和链式存储的特点。每个顶点对应一个链表链表中存储与该顶点直接相连的其他顶点。这种表示法的空间复杂度为O(ne)其中n是顶点数e是边数。typedef struct ArcNode { // 边结点 int adjvex; // 该边所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条边的指针 int weight; // 边的权值带权图 } ArcNode; typedef struct VNode { // 顶点结点 int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的边 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vertexNum, edgeNum; // 当前顶点数和边数 } ALGraph;在实际应用中选择哪种存储结构需要考虑图的特点和需要支持的操作。例如频繁查询边存在性的场景适合邻接矩阵而需要遍历所有邻接点的场景则邻接表更高效。1.2 图的遍历算法实现深度优先搜索DFS类似于树的先序遍历采用递归或栈实现。其基本思想是从某个顶点出发尽可能深地探索图的分支直到当前分支的所有顶点都被访问过然后回溯到前一个顶点继续探索。// 邻接矩阵的DFS实现 void DFS(MGraph G, int v, int visited[]) { visited[v] 1; printf(%d , G.vertex[v]); // 访问顶点v for (int i 0; i G.vertexNum; i) { if (G.edge[v][i] ! 0 !visited[i]) { // v和i之间有边且i未被访问 DFS(G, i, visited); } } }广度优先搜索BFS则类似于树的层次遍历使用队列实现。它从起始顶点开始先访问所有邻接点然后再依次访问这些邻接点的邻接点以此类推。// 邻接表的BFS实现 void BFS(ALGraph G, int v) { int visited[MAX_VERTEX_NUM] {0}; Queue Q; InitQueue(Q); visited[v] 1; EnQueue(Q, v); while (!QueueEmpty(Q)) { int u; DeQueue(Q, u); printf(%d , G.vertices[u].data); // 访问顶点u for (ArcNode *p G.vertices[u].firstarc; p; p p-nextarc) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; EnQueue(Q, p-adjvex); } } } }在实际应用中DFS适合寻找图中的路径、检测环路等场景而BFS则更适合寻找最短路径无权图或层次遍历等场景。在PTA题目中这两种算法经常作为基础工具用于解决更复杂的问题。2. 图论算法的典型应用2.1 最短路径问题Dijkstra算法是解决单源最短路径问题的经典算法适用于边权非负的有向图或无向图。算法采用贪心策略逐步确定从源点到其他各顶点的最短路径。void Dijkstra(MGraph G, int v0, int dist[], int path[]) { int final[MAX_VERTEX_NUM] {0}; for (int i 0; i G.vertexNum; i) { dist[i] G.edge[v0][i] ? G.edge[v0][i] : INT_MAX; path[i] (dist[i] INT_MAX) ? v0 : -1; } dist[v0] 0; final[v0] 1; for (int i 1; i G.vertexNum; i) { int min INT_MAX, v -1; for (int j 0; j G.vertexNum; j) { if (!final[j] dist[j] min) { min dist[j]; v j; } } if (v -1) break; final[v] 1; for (int j 0; j G.vertexNum; j) { if (!final[j] G.edge[v][j] dist[v] G.edge[v][j] dist[j]) { dist[j] dist[v] G.edge[v][j]; path[j] v; } } } }Floyd算法则用于解决所有顶点对之间的最短路径问题其核心思想是动态规划。算法通过逐步考虑中间顶点来更新最短路径估计。void Floyd(MGraph G, int dist[][MAX_VERTEX_NUM], int path[][MAX_VERTEX_NUM]) { for (int i 0; i G.vertexNum; i) { for (int j 0; j G.vertexNum; j) { dist[i][j] G.edge[i][j] ? G.edge[i][j] : INT_MAX; path[i][j] (dist[i][j] INT_MAX) ? i : -1; } dist[i][i] 0; } for (int k 0; k G.vertexNum; k) { for (int i 0; i G.vertexNum; i) { for (int j 0; j G.vertexNum; j) { if (dist[i][k] ! INT_MAX dist[k][j] ! INT_MAX dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; path[i][j] path[k][j]; } } } } }在PTA题目中最短路径问题常以交通网络、路由选择等实际场景出现。解题时需要注意图的表示方式邻接矩阵或邻接表、边权的处理特别是负权边的情况以及路径重建的方法。2.2 最小生成树问题Prim算法和Kruskal算法是解决最小生成树问题的两种主要方法。Prim算法类似于Dijkstra算法从一个顶点开始逐步扩展生成树而Kruskal算法则按边权从小到大选择边确保不形成环路。// Prim算法实现 void Prim(MGraph G, int parent[]) { int lowcost[MAX_VERTEX_NUM]; int closest[MAX_VERTEX_NUM]; for (int i 0; i G.vertexNum; i) { lowcost[i] G.edge[0][i] ? G.edge[0][i] : INT_MAX; closest[i] 0; } lowcost[0] 0; parent[0] -1; for (int i 1; i G.vertexNum; i) { int min INT_MAX, k -1; for (int j 0; j G.vertexNum; j) { if (lowcost[j] ! 0 lowcost[j] min) { min lowcost[j]; k j; } } if (k -1) break; parent[k] closest[k]; lowcost[k] 0; for (int j 0; j G.vertexNum; j) { if (lowcost[j] ! 0 G.edge[k][j] G.edge[k][j] lowcost[j]) { lowcost[j] G.edge[k][j]; closest[j] k; } } } }Kruskal算法的实现通常需要借助并查集Disjoint Set UnionDSU数据结构来高效地检测环路。在PTA题目中最小生成树问题常出现在网络设计、电路布线等场景中。3. 图论中的高级算法与应用3.1 拓扑排序与关键路径拓扑排序是针对有向无环图DAG的线性排序算法使得对于图中的每一条有向边(u,v)u在排序中总是位于v的前面。这种排序在任务调度、课程安排等场景中非常有用。// 邻接表的拓扑排序实现 bool TopologicalSort(ALGraph G, int topo[]) { int indegree[MAX_VERTEX_NUM] {0}; for (int i 0; i G.vertexNum; i) { for (ArcNode *p G.vertices[i].firstarc; p; p p-nextarc) { indegree[p-adjvex]; } } Stack S; InitStack(S); for (int i 0; i G.vertexNum; i) { if (indegree[i] 0) Push(S, i); } int count 0; while (!StackEmpty(S)) { int u; Pop(S, u); topo[count] u; for (ArcNode *p G.vertices[u].firstarc; p; p p-nextarc) { int v p-adjvex; if (--indegree[v] 0) Push(S, v); } } return count G.vertexNum; }关键路径算法AOE网络则在拓扑排序的基础上计算工程中的关键活动这些活动的延迟将直接影响整个工程的完成时间。在PTA题目中这类问题常以项目规划、工序安排等形式出现。3.2 网络流算法最大流问题是图论中的经典问题Ford-Fulkerson方法及其改进算法如Edmonds-Karp算法是解决这一问题的有效方法。这些算法在交通流量优化、网络带宽分配等方面有重要应用。// Edmonds-Karp算法实现 int EdmondsKarp(MGraph G, int s, int t) { int flow[MAX_VERTEX_NUM][MAX_VERTEX_NUM] {0}; int max_flow 0; while (true) { int parent[MAX_VERTEX_NUM] {-1}; Queue Q; InitQueue(Q); EnQueue(Q, s); parent[s] s; while (!QueueEmpty(Q)) { int u; DeQueue(Q, u); for (int v 0; v G.vertexNum; v) { if (parent[v] -1 G.edge[u][v] flow[u][v]) { parent[v] u; if (v t) break; EnQueue(Q, v); } } if (parent[t] ! -1) break; } if (parent[t] -1) break; int path_flow INT_MAX; for (int v t; v ! s; v parent[v]) { int u parent[v]; path_flow min(path_flow, G.edge[u][v] - flow[u][v]); } for (int v t; v ! s; v parent[v]) { int u parent[v]; flow[u][v] path_flow; flow[v][u] - path_flow; } max_flow path_flow; } return max_flow; }在PTA题目中网络流问题可能以资源分配、匹配问题等形式出现。解题时需要正确建立流网络模型并选择合适的算法实现。4. PTA图论题目的解题技巧与常见问题4.1 输入处理与图构建PTA图论题目通常需要从输入数据构建图结构。常见的输入格式包括第一行给出顶点数n和边数m随后m行每行给出边的信息可能有起点、终点、权值有时顶点编号从0开始有时从1开始// 典型的图构建代码 MGraph BuildGraph() { MGraph G; scanf(%d %d, G.vertexNum, G.edgeNum); for (int i 0; i G.vertexNum; i) { G.vertex[i] i; // 假设顶点编号与数组下标一致 } // 初始化邻接矩阵 for (int i 0; i G.vertexNum; i) { for (int j 0; j G.vertexNum; j) { G.edge[i][j] 0; // 初始时无边 } } // 读入边信息 for (int k 0; k G.edgeNum; k) { int i, j, w; scanf(%d %d %d, i, j, w); G.edge[i][j] w; G.edge[j][i] w; // 如果是无向图 } return G; }常见问题包括顶点编号处理不当如从1开始的编号直接用作数组下标有向图和无向图的边处理混淆多重边或自环边的特殊处理顶点或边数非常大的情况下的效率问题4.2 算法选择与优化针对不同的问题特点需要选择合适的算法小规模图n≤100可以使用邻接矩阵和简单的Floyd算法中等规模图100n≤1000需要考虑邻接表和更高效的算法大规模图n1000可能需要使用堆优化Dijkstra、并查集优化Kruskal等// 堆优化Dijkstra示例 typedef struct { int v; int dist; } HeapNode; void Dijkstra_Heap(ALGraph G, int s, int dist[]) { PriorityQueue H; InitQueue(H); for (int i 0; i G.vertexNum; i) { dist[i] INT_MAX; } dist[s] 0; EnQueue(H, (HeapNode){s, 0}); while (!QueueEmpty(H)) { HeapNode u; DeQueue(H, u); if (u.dist dist[u.v]) continue; for (ArcNode *p G.vertices[u.v].firstarc; p; p p-nextarc) { int v p-adjvex; if (dist[v] dist[u.v] p-weight) { dist[v] dist[u.v] p-weight; EnQueue(H, (HeapNode){v, dist[v]}); } } } }4.3 常见错误与调试技巧在解决PTA图论题目时常见的错误包括数组越界特别是顶点编号处理不当无限循环BFS/DFS中未正确标记已访问顶点逻辑错误有向图当作无向图处理或反之边界条件空图、单顶点图等特殊情况未处理调试技巧使用小规模测试数据手工验证打印中间结果如邻接矩阵、距离数组等对特殊输入情况进行单独测试使用PTA的自测功能检查样例提示在PTA提交前务必测试以下特殊情况顶点数为0或1的图边数为0的图只有孤立顶点完全图所有顶点间都有边存在重边或自环的图根据题目要求处理4.4 性能优化建议对于PTA中的大规模图论题目可以考虑以下优化使用更高效的输入输出方法如用scanf/printf代替cin/cout选择合适的存储结构稀疏图用邻接表稠密图用邻接矩阵避免不必要的初始化操作使用位运算替代某些算术运算合理使用内存避免过度预分配// 快速输入优化示例 inline int read() { int x 0, f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 ch - 0; ch getchar(); } return x * f; } // 在main函数中使用 int n read(); int m read();通过系统学习图论的基本概念、算法实现和解题技巧结合PTA平台的实践练习可以逐步掌握数据结构与算法课程中的图论内容。在实际编程中要注意算法的适用场景、时间复杂度和空间复杂度根据问题特点选择最合适的解决方案。