尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

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

发布时间：2026/10/31 10:20:42 尧图网站建设
图论基础：数据结构与算法中的图存储与遍历

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(n+e)，其中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 Union，DSU）数据结构来高效地检测环路。在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. 顶点编号处理不当（如从1开始的编号直接用作数组下标）
  2. 有向图和无向图的边处理混淆
  3. 多重边或自环边的特殊处理
  4. 顶点或边数非常大的情况下的效率问题

4.2 算法选择与优化

针对不同的问题特点，需要选择合适的算法：

  • 小规模图（n≤100）：可以使用邻接矩阵和简单的Floyd算法
  • 中等规模图（100<n≤1000）：需要考虑邻接表和更高效的算法
  • 大规模图（n>1000）：可能需要使用堆优化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图论题目时，常见的错误包括：

  1. 数组越界：特别是顶点编号处理不当
  2. 无限循环：BFS/DFS中未正确标记已访问顶点
  3. 逻辑错误：有向图当作无向图处理，或反之
  4. 边界条件：空图、单顶点图等特殊情况未处理

调试技巧：

  • 使用小规模测试数据手工验证
  • 打印中间结果（如邻接矩阵、距离数组等）
  • 对特殊输入情况进行单独测试
  • 使用PTA的"自测"功能检查样例

提示：在PTA提交前，务必测试以下特殊情况：

  1. 顶点数为0或1的图
  2. 边数为0的图（只有孤立顶点）
  3. 完全图（所有顶点间都有边）
  4. 存在重边或自环的图（根据题目要求处理）

4.4 性能优化建议

对于PTA中的大规模图论题目，可以考虑以下优化：

  1. 使用更高效的输入输出方法（如用scanf/printf代替cin/cout）
  2. 选择合适的存储结构（稀疏图用邻接表，稠密图用邻接矩阵）
  3. 避免不必要的初始化操作
  4. 使用位运算替代某些算术运算
  5. 合理使用内存（避免过度预分配）
// 快速输入优化示例 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平台的实践练习，可以逐步掌握数据结构与算法课程中的图论内容。在实际编程中，要注意算法的适用场景、时间复杂度和空间复杂度，根据问题特点选择最合适的解决方案。

网站建设 视觉设计 SEO优化
返回列表