【数据结构】图的应用：最小生成树；最短路径；有向无环图描述表达式；拓扑排序；逆拓扑排序；关键路径

您所在的位置：网站首页 › 关键路径的画法有哪些 › 【数据结构】图的应用：最小生成树；最短路径；有向无环图描述表达式；拓扑排序；逆拓扑排序；关键路径

【数据结构】图的应用：最小生成树；最短路径；有向无环图描述表达式；拓扑排序；逆拓扑排序；关键路径

2024-07-12 10:04| 来源: 网络整理| 查看: 265

1、最小生成树

1.1 概念

1.2 普利姆算法（Prim）

1.3 克鲁斯卡尔算法（Kruskal）

2、最短路径

2.1 迪杰斯特拉算法（Dijkstra）

2.2 弗洛伊德算法（Floyd）

2.3 BFS算法，Dijkstra算法，Floyd算法的对比

3、有向无环图描述表达式

3.1 有向无环图定义及特点

3.2 描述表达式

4、拓扑排序

4.1 AOV网

4.2 步骤

4.3 DFS实现拓扑排序

5、逆拓扑排序

5.1 步骤

5.2 DFS实现逆拓扑排序

6、关键路径

6.1 AOE网

6.2 求解方法

6.3 特性

1、最小生成树 1.1 概念

最小生成树是一种基于图的算法，用于在一个连通加权无向图中找到一棵生成树，使得树上所有边的权重之和最小。最小生成树指一张无向图的生成树中边权最小的那棵树。生成树是指一张无向图的一棵极小连通子图，它包含了原图的所有顶点，但只有足以构成一棵树的 n-1 条边。最小生成树可以用来解决最小通信代价、最小电缆费用、最小公路建设等问题。常见的求解最小生成树的算法有Prim算法和Kruskal算法。

1.2 普利姆算法（Prim）

Prim算法的基本思想是从一个任意顶点开始，每次添加一个距离该顶点最近的未访问过的顶点和与之相连的边，直到所有顶点都被访问过。

其基本步骤如下：

初始化：定义一个空的集合S表示已经确定为最小生成树的结点集合，和一个数组dist表示当前结点到S集合中最短距离，初始时S集合为空，数组dist中所有元素为正无穷，将任意一个结点u加到S集合中。

找到到S集合距离最近的结点v，并将v加入到S集合中。

更新数组dist，更新S集合中的结点到其它结点的距离。对于所有不在S集合中的结点w，如果从v到w的距离小于dist[w]，则更新dist[w]的值为从v到w的距离。

重复以上步骤2和步骤3，直到所有的结点都加入到S集合中，即构成了最小生成树。

该算法的时间复杂度为O(n^2)，其中n为图的顶点数。

以下是用C语言实现Prim算法的代码，假设图的节点从0到n-1编号。

#include #include #include #define MAX_N 1000 // 最大顶点数 #define INF INT_MAX // 正无穷 #define false 0 #define true 1 // 无向图的邻接矩阵表示法 int graph[MAX_N][MAX_N]; // 图的邻接矩阵 int visited[MAX_N]; // 标记结点是否已加入最小生成树 int dist[MAX_N]; // 记录结点到最小生成树的距离 int parent[MAX_N]; // 记录结点的父节点（即最小生成树的边） int prim(int n) { // 初始化 for (int i = 0; i < n; i++) { visited[i] = false; dist[i] = INF; parent[i] = -1; } dist[0] = 0; // 从结点0开始构建最小生成树 for (int i = 0; i < n - 1; i++) { // n - 1次循环 int min_dist = INF; int min_index = -1; // 找出距离最小生成树最近的结点 for (int j = 0; j < n; j++) { if (!visited[j] && dist[j] < min_dist) { min_dist = dist[j]; min_index = j; } } if (min_index == -1) { break; // 找不到未访问的结点，算法结束 } visited[min_index] = true; // 更新未加入最小生成树的结点到最小生成树的距离和父节点 for (int j = 0; j < n; j++) { if (!visited[j] && graph[min_index][j] < dist[j]) { dist[j] = graph[min_index][j]; parent[j] = min_index; } } } // 输出最小生成树 int cost = 0; for (int i = 1; i < n; i++) { printf("%d -> %d : %d\n", parent[i], i, graph[i][parent[i]]); cost += graph[i][parent[i]]; } return cost; } int main() { int n; // 结点数量 int m; // 边数量 scanf("%d%d", &n, &m); // 初始化邻接矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { graph[i][j] = INF; } } // 读入边 for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); graph[u][v] = w; graph[v][u] = w; // 无向图，所以要加上反向边 } int cost = prim(n); printf("cost = %d\n", cost); return 0; }

dist数组记录的是结点到最小生成树的距离，parent数组记录的是结点的父节点，visited数组记录结点是否已加入最小生成树。在每次循环中，找出距离最小生成树最近的结点，并将其标记为已访问，再更新未加入最小生成树的结点到最小生成树的距离和父节点。最后输出最小生成树的边，以及最小生成树的总权值（即边的权值之和）。

1.3 克鲁斯卡尔算法（Kruskal）

Kruskal算法的基本思想是先将图中所有边按边权从小到大排序，然后逐个加入到生成树中，但是要保证加入后生成树仍然是无环的。如果加入某一条边形成了环，则不加入该边，继续考虑下一条边。

步骤如下：

将所有边按照边权从小到大排序；初始化一个空的树；从排序后的边列表中选择权重最小的边，并判断这条边的两个端点是否在同一棵树中；如果这条边的两个端点不在同一棵树中，则将这条边加入最小生成树中，并将这两个端点所在的树合并成一棵树；重复步骤3和步骤4，直到所有的边都被考虑过。

以下是用C语言实现Kruskal算法的代码，假设图的节点从0到n-1编号。

#include #include #include #define MAX_N 1000 // 最大顶点数 #define INF INT_MAX // 正无穷 #define false 0 #define true 1 // 边的结构体 typedef struct Edge { int u; int v; int w; } Edge; Edge edges[MAX_N * MAX_N]; // 边集合 int parent[MAX_N]; // 记录结点的父节点 int rank[MAX_N]; // 记录结点所在集合的秩 int cmp(const void* a, const void* b) { Edge* edge1 = (Edge*)a; Edge* edge2 = (Edge*)b; return edge1->w - edge2->w; } int find(int x) { // 路径压缩 if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { // 按秩合并 int root_x = find(x); int root_y = find(y); if (rank[root_x] < rank[root_y]) { parent[root_x] = root_y; } else { parent[root_y] = root_x; if (rank[root_x] == rank[root_y]) { rank[root_x]++; } } } int kruskal(int n, int m) { // 初始化 for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } // 按边权从小到大排序 qsort(edges, m, sizeof(Edge), cmp); // 构建最小生成树 int cost = 0; int count = 0; for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; int w = edges[i].w; if (find(u) != find(v)) { // 判断是否在同一个集合中 unite(u, v); cost += w; count++; if (count == n - 1) { // 边数等于n-1，生成树构建完成 break; } } } // 输出最小生成树边 for (int i = 0; i < n; i++) { if (parent[i] == i) { // 找到根节点 for (int j = 0; j < m; j++) { if ((edges[j].u == i && parent[edges[j].v] == i) || (edges[j].v == i && parent[edges[j].u] == i)) { printf("%d -> %d : %d\n", edges[j].u, edges[j].v, edges[j].w); } } } } return cost; } int main() { int n; // 结点数量 int m; // 边数量 scanf("%d%d", &n, &m); // 读入边并构建边集合 for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); edges[i].u = u; edges[i].v = v; edges[i].w = w; } int cost = kruskal(n, m); printf("cost = %d\n", cost); return 0; }

其中，边的结构体包括起点、终点和边权。在Kruskal算法中，先对边按照权值从小到大进行排序，每次取出最小的边，如果它不连通任何已经选出的边，则加入最小生成树中。为了判断两个结点是否在同一个集合中，可以使用并查集的数据结构，其中parent数组记录结点的父节点，rank数组记录结点所在集合的秩。并查集的find和unite函数实现路径压缩和按秩合并。最后输出最小生成树的边，以及最小生成树的总权值（即边的权值之和）。

2、最短路径 2.1 迪杰斯特拉算法（Dijkstra）

Dijkstra算法是一种解决单源最短路径问题的贪心算法，它的基本思路是从起点开始，每次选择当前最短路径中的一个顶点，然后更新它的邻居的最短路径。

以下是Dijkstra算法的详细步骤：

初始化数据结构：创建一个距离数组dist，用来记录起点到每个顶点的最短距离，初始化为正无穷；创建一个visited数组，记录每个顶点是否被访问过；创建一个前驱数组path，记录每个顶点的前驱顶点。

将起点的dist设为0，将visited设为false，将path设为null。

对于起点的所有邻居，更新它们的dist为起点到邻居的距离，并将它们的path设为起点。

重复以下步骤，直到所有顶点都被访问过： a. 从未被访问过的顶点中，选择dist最小的顶点作为当前顶点。 b. 将当前顶点设为已访问。 c. 对当前顶点的所有邻居，如果当前顶点到邻居的距离比邻居的dist值小，就更新邻居的dist值和path值。

通过prev数组可找到从起点到任意顶点的最短路径。

下面是一个使用C语言实现Dijkstra算法的示例：

#include #include #define V 6 // 顶点数 // 寻找dist数组中最小值对应的下标 int minDistance(int dist[], bool visited[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (visited[v] == false && dist[v] dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = path[k][j]; /* i 到 j 的路径经过 u 的话，i 到 k 的路径就经过 u 了，于是将 i 到 k 的路径经过的节点挂到 i 到 j 的路径上 */ } } } } } void print_path(int u, int v) { if (path[u][v] == -1) { /* i 到 j 没有中间节点 */ printf("%d", v); } else { /* i 到 j 的路径经过 u */ print_path(u, path[u][v]); /* 递归打印 i 到 u 的路径 */ printf("->%d", v); } } int main() { int n; scanf("%d", &n); floyd(n); int s, t; scanf("%d %d", &s, &t); printf("%d\n", dist[s][t]); print_path(s, t); return 0; }

该代码首先读入图的规模 n，然后读入每条边的起点、终点和边权值，根据这些信息构建邻接矩阵。然后，它使用Floyd算法计算任意两点之间的最短路径和路径矩阵。最后，给定起点 s 和终点 t，输出它们之间的最短路程和路径。

2.3 BFS算法，Dijkstra算法，Floyd算法的对比

3、有向无环图描述表达式 3.1 有向无环图定义及特点

有向无环图（Directed Acyclic Graph，简称DAG）是一种有向图，其中不存在环路，即从任意一个顶点出发不可能经过若干条边回到此顶点。通常用来表示任务调度、依赖关系等场景，具有以下特点：

1. 有向性：DAG中所有边均有方向，即起点指向终点。

2. 无环性：DAG中不存在环路，即不能从一个顶点出发沿其周游返回此顶点。

3. 顶点与边的关系：DAG中的顶点表示任务、事件、状态等，边表示依赖关系、控制关系等。

4. 拓扑排序：DAG可以进行拓扑排序，即将DAG中所有顶点排序，使得对于任意一条边(u,v)，顶点u都排在v的前面。

3.2 描述表达式

有向无环图可以用于描述表达式的计算顺序，其中每个节点表示一个操作符或操作数，每个有向边表示操作数或操作符之间的依赖关系和计算顺序。

例如，对于表达式 "5*(2+3)":

首先，将 "+" 表示为一个节点，并有两个入边和一条出边；然后，将 "2" 和 "3" 也表示为节点，并分别与 "+" 节点相连；接着，再将 "*" 表示为节点，并与 "5" 和 "+" 节点相连；最后，整个有向无环图如图所示：

+ // "+" 节点 / \ / \ 2 3 // "2" 和 "3" 节点 \ / \ / * // "*" 节点 | 5 // "5" 节点

按照拓扑排序的顺序遍历这个有向无环图，就可以得到表达式的计算顺序：2 -> 3 -> + -> 5 -> *，即先计算 2 和 3 的和，再将结果与 5 相乘，最后得到结果 25。

4、拓扑排序 4.1 AOV网

4.2 步骤

拓扑排序是对有向图进行排序的一种算法，步骤如下：

1. 初始化：首先，将所有入度为0的顶点加入到一个队列中。

2. 遍历：从队列中取出一个顶点，输出该顶点并删除该顶点的所有出边（即将它所指向的顶点的入度减1）。如果该顶点删除后所指向的结点入度为0，则将其加入队列中。

3. 重复遍历：重复以上操作，直到队列为空为止。

4. 判断：如果输出的顶点数等于图中的顶点数，则拓扑排序成功，并输出结果；否则，图中存在环，拓扑排序失败。

4.3 DFS实现拓扑排序

DFS实现拓扑排序的基本思路是：从任意一个没有后继节点的节点出发，沿着它的各个链路不断深入，并记录经过的节点，直到到达一个没有出边的节点为止。在返回的过程中，将经过的节点依次加入结果数组中，直到所有的节点都加入到结果数组中。

DFS实现拓扑排序的C语言代码示例：

#include #include #define MAXN 1000 int n, m; int G[MAXN][MAXN]; //邻接矩阵存图 int vis[MAXN], res[MAXN], idx = 0; //vis数组用于记录是否访问过，res数组用于存储结果 void dfs(int u){ vis[u] = 1; //标记为已访问 for(int v = 0; v < n; v++){ if(G[u][v] && !vis[v]){ //如果v是u的后继节点且未被访问过 dfs(v); //继续深入 } } res[idx++] = u; //将该节点存入结果数组中 } void topSort(){ for(int i = 0; i < n; i++){ if(!vis[i]){ //从未被访问过的节点出发 dfs(i); } } for(int i = n - 1; i >= 0; i--){ //倒序输出结果数组 printf("%d ", res[i]); } } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); G[u][v] = 1; //有向边 } topSort(); return 0; }

其中，G数组为邻接矩阵存储图，vis数组用于记录是否访问过，res数组用于存储结果，idx为结果数组的下标。topSort函数是主要的拓扑排序算法，遍历所有节点并调用dfs函数，dfs函数通过递归的方式实现深度优先遍历。最后，倒序输出结果数组，即可得到拓扑排序的结果。

5、逆拓扑排序 5.1 步骤

逆拓扑排序是指在一个有向无环图中，对于每个节点v，输出所有能够到达v的节点。逆拓扑排序的步骤如下：

1. 初始化一个空的结果列表和一个空的队列。 2. 对于每个节点v，计算能够到达v的节点数目，记为out_degree[v]。 3. 将所有out_degree[v]为0（出度为0）的节点加入队列。 4. 当队列非空时，取出队首节点u，并将其加入结果列表。 5. 对于u的每个邻居节点v，将out_degree[v]减1。 6. 若out_degree[v]等于0，则将v加入队列。 7. 重复步骤4-6直到队列为空。 8. 返回结果列表。

5.2 DFS实现逆拓扑排序

逆拓扑排序指的是在一个有向无环图(DAG)中，对所有节点进行排序，使得对于任意一条有向边(u, v)，都有排在前面的节点先于排在后面的节点。逆拓扑排序可以通过深度优先搜索(DFS)实现。具体实现步骤如下：

定义一个数组visited，用于记录每个节点是否已经被访问过，初始值为0。

定义一个栈stack，用于存储已经访问过的节点。

对于每个节点u，进行DFS搜索，具体步骤如下：

a. 标记节点u已经被访问过，visited[u]=1。

b. 对于节点u的每个邻接节点v，如果该节点还没有被访问过，则进行DFS搜索。

c. 将节点u入栈。

当所有节点都搜索完毕后，从栈顶开始按顺序取出节点，生成逆拓扑排序结果。

下面是C语言实现代码：

#include #define MAX_VERTEX_NUM 100 int visited[MAX_VERTEX_NUM], topo[MAX_VERTEX_NUM], top = -1; int vex_num, arc_num; int Graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; void DFS(int u) { visited[u] = 1; int v; for (v = 0; v < vex_num; v++) { if (Graph[u][v] == 1 && visited[v] == 0) { DFS(v); } } topo[++top] = u; } void TopoSort() { int i, j; for (i = 0; i < vex_num; i++) { visited[i] = 0; } top = -1; for (i = 0; i < vex_num; i++) { if (visited[i] == 0) { DFS(i); } } printf("逆拓扑排序结果："); for (i = vex_num - 1; i >= 0; i--) { printf("%d ", topo[i]); } } int main() { int i, j, u, v; scanf("%d%d", &vex_num, &arc_num); for (i = 0; i < vex_num; i++) { for (j = 0; j < vex_num; j++) { Graph[i][j] = 0; } } for (i = 0; i < arc_num; i++) { scanf("%d%d", &u, &v); Graph[u][v] = 1; } TopoSort(); return 0; }

示例输入：

7 10 0 1 0 2 1 3 1 5 1 4 2 5 3 6 4 6 5 4 5 6

示例输出：

逆拓扑排序结果：0 2 1 5 4 3 6 6、关键路径 6.1 AOE网