数据结构之图的应用场景及其代码

一，最小生成树

最小生成树（Minimum Spanning Tree, MST）是图论中的经典问题，旨在通过选择无向连通图中的边，使得所有节点连通且总边权最小。

1.1 普里姆（Prim）算法

普里姆算法是一种用于求解无向连通加权图的最小生成树（MST）的经典贪心算法。其核心思想是从任意一个顶点出发，逐步选择与当前生成树连接的最短边，直到包含图中所有顶点。该算法适用于稠密图（边数较多），时间复杂度通常为 O(V2)（利用邻接矩阵）或 O(ElogV)（利用优先队列优化），其中 V 为顶点数，E 为边数.

1.1.1算法步骤：

1. 初始化：

   • 选择任意一个顶点作为起点，加入最小生成树集合 S。
   • 初始化一个数组（或字典）记录每个顶点到生成树的最小边权（初始时，起点的距离为 0，其余顶点为无穷大）。

2. 迭代扩展生成树：

   • 从所有不在 S 中的顶点中，选择到 S 距离最小的顶点 u，加入 S。
   • 遍历 u 的所有邻接顶点 v，若 v 不在 S 中且边权 w(u,v) 小于 v 到 S 的当前最小距离，则更新 v 的距离为 w(u,v)。

3. 终止条件：

   • 当所有顶点都加入 S 时，算法结束，此时所选边构成最小生成树。

1.1.2 示例代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>  // 添加INT_MAX的定义#define MAX_VERTEX_NUM 20  // 最大顶点数// 图的邻接矩阵存储结构
typedef struct {char vexs[MAX_VERTEX_NUM];          // 顶点向量int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵int vexnum, arcnum;       // 图的顶点数和边数
} MGraph;// 普里姆算法，从顶点u出发构造最小生成树
void Prim(MGraph G, int u) {int min, i, j, k;int adjvex[MAX_VERTEX_NUM];       // 保存相关顶点下标int lowcost[MAX_VERTEX_NUM];      // 保存相关顶点间边的权值// 检查输入顶点是否合法if (u < 0 || u >= G.vexnum) {printf("Error: Invalid vertex index %d\n", u);return;}// 初始化lowcost和adjvex数组for (i = 0; i < G.vexnum; i++) {lowcost[i] = G.arc[u][i];  // 初始化为顶点u到各顶点的边权adjvex[i] = u;             // 初始时所有顶点的前驱均为u}lowcost[u] = 0;  // 顶点u加入生成树printf("Prim MST edges:\n");for (i = 1; i < G.vexnum; i++) {  // 找剩下的G.vexnum-1个顶点min = INT_MAX;k = -1;  // 初始化k为无效值// 寻找当前最小边for (j = 0; j < G.vexnum; j++) {if (lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;  // k记录当前最小边的顶点下标}}// 如果找不到最小边，说明图不连通if (k == -1) {printf("Error: Graph is not connected!\n");return;}printf("(%c, %c) 权值:%d\n", G.vexs[adjvex[k]], G.vexs[k], min);lowcost[k] = 0;  // 顶点k加入生成树// 更新lowcost数组和adjvex数组for (j = 0; j < G.vexnum; j++) {if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {lowcost[j] = G.arc[k][j];  // 保留更小的边权adjvex[j] = k;             // 记录新的前驱顶点}}}
}// 打印邻接矩阵（辅助调试）
void printAdjMatrix(MGraph G) {printf("邻接矩阵:\n");for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++) {if (G.arc[i][j] == INT_MAX)printf("INF\t");elseprintf("%d\t", G.arc[i][j]);}printf("\n");}
}int main() {MGraph G;int i, j;// 初始化顶点数和边数G.vexnum = 5;G.arcnum = 8;// 初始化顶点向量G.vexs[0] = 'A';G.vexs[1] = 'B';G.vexs[2] = 'C';G.vexs[3] = 'D';G.vexs[4] = 'E';// 初始化邻接矩阵（权值为INT_MAX表示无直接边）for (i = 0; i < G.vexnum; i++) {for (j = 0; j < G.vexnum; j++) {if (i == j)G.arc[i][j] = 0;  // 自己到自己的距离为0elseG.arc[i][j] = INT_MAX;}}// 添加边的权值（无向图对称）G.arc[0][1] = 10;G.arc[0][2] = 15;G.arc[0][3] = 20;G.arc[1][2] = 3;G.arc[1][4] = 25;G.arc[2][3] = 4;G.arc[2][4] = 2;G.arc[3][4] = 6;// 对称矩阵赋值for (i = 0; i < G.vexnum; i++) {for (j = i + 1; j < G.vexnum; j++) {G.arc[j][i] = G.arc[i][j];}}// 打印邻接矩阵（调试用）printAdjMatrix(G);// 从顶点A(0)开始执行Prim算法printf("\n从顶点%c开始的最小生成树:\n", G.vexs[0]);Prim(G, 0);// 验证从不同顶点开始的结果是否一致printf("\n从顶点%c开始的最小生成树:\n", G.vexs[2]);Prim(G, 2);return 0;
}

1.1.3 普里姆算法的应用场景

普里姆算法因其 “从局部扩展全局” 的特性，在以下场景中表现优异：

1. 通信网络与电力网络设计

• 场景：构建光纤网络、电力传输网络时，需连接所有节点（如城市、基站）并最小化线路总长度或成本。
• 应用：
  • 节点密集（如城区内的基站）时，普里姆算法可高效找到最短连接方案。
  • 案例：某城市规划 5G 基站网络，已知各基站间的建设成本（边权），使用普里姆算法从市中心基站出发，逐步连接周边基站，确保总建设成本最低。

#include "prim_algorithm.h"// 应用场景1: 通信网络设计
void communicationNetworkDesign(int num_nodes) {printf("\n--- 应用1: 通信网络设计 ---\n");Graph graph;initGraph(&graph, num_nodes);// 随机生成通信网络连接和成本srand(time(NULL));for (int i = 0; i < num_nodes; i++) {for (int j = i + 1; j < num_nodes; j++) {if (rand() % 2 == 0) {  // 50%概率连接int cost = rand() % 100 + 1;  // 成本1-100addEdge(&graph, i, j, cost);}}}// 计算最小生成树int mst_size;Edge *mst = primMST(&graph, &mst_size);int total_cost = calculateTotalWeight(mst, mst_size);printf("通信网络设计结果（%d个节点）:\n", num_nodes);printf("总建设成本: %d\n", total_cost);printf("连接方案:\n");for (int i = 0; i < mst_size; i++) {printf("  城市%d <-> 城市%d (成本: %d)\n", mst[i].src, mst[i].dest, mst[i].weight);}free(mst);
}    

2. 电路与芯片设计

• 场景：印刷电路板（PCB）或集成电路中，需用最短导线连接元件（如电阻、电容）。
• 应用：
  • 将元件视为顶点，导线长度或电阻值视为边权，普里姆算法可优化布线，减少材料消耗和信号延迟。
  • 优势：在元件密集的芯片设计中，邻接矩阵表示法配合普里姆算法可快速生成最优连接。

#include "prim_algorithm.h"// 应用场景2: 电路布线优化
void circuitWiringOptimization(int num_components) {printf("\n--- 应用2: 电路布线优化 ---\n");Graph graph;initGraph(&graph, num_components);// 随机生成元件位置Point *components = (Point*)malloc(num_components * sizeof(Point));if (!components) {printf("内存分配失败\n");exit(1);}srand(time(NULL));for (int i = 0; i < num_components; i++) {components[i].x = rand() % 100;components[i].y = rand() % 100;}// 计算元件间的欧氏距离作为连接成本for (int i = 0; i < num_components; i++) {for (int j = i + 1; j < num_components; j++) {int dx = components[i].x - components[j].x;int dy = components[i].y - components[j].y;int distance = (int)sqrt(dx * dx + dy * dy);addEdge(&graph, i, j, distance);}}// 计算最小生成树int mst_size;Edge *mst = primMST(&graph, &mst_size);int total_length = calculateTotalWeight(mst, mst_size);printf("电路布线优化结果（%d个元件）:\n", num_components);printf("总导线长度: %d\n", total_length);free(mst);free(components);
}    

3. 物流与交通网络优化

• 场景：物流中心与配送点的路线规划，要求总运输距离最短。
• 应用：
  • 当配送点分布密集（如城市内的多个仓库与客户点），普里姆算法可从某个枢纽出发，逐步连接最近的配送点，降低总行驶里程。
  • 案例：某快递公司以市中心仓库为起点，使用普里姆算法规划周边网点的最短配送路线网络。

#include "prim_algorithm.h"// 应用场景3: 物流网络规划
void logisticsNetworkPlanning(int num_sites) {printf("\n--- 应用3: 物流网络规划 ---\n");Graph graph;initGraph(&graph, num_sites);// 随机生成物流站点和运输成本srand(time(NULL));for (int i = 0; i < num_sites; i++) {for (int j = i + 1; j < num_sites; j++) {int distance = rand() % 200 + 10;  // 距离10-200公里addEdge(&graph, i, j, distance);}}// 计算最小生成树int mst_size;Edge *mst = primMST(&graph, &mst_size);int total_distance = calculateTotalWeight(mst, mst_size);printf("物流网络规划结果（%d个站点）:\n", num_sites);printf("总运输距离: %d\n", total_distance);free(mst);
}    

4. 游戏开发与地图生成

• 场景：生成连通的游戏地图（如迷宫、开放世界路径）。
• 应用：
  • 迷宫生成：用普里姆算法从起点房间开始，随机选择相邻未访问的房间打通墙壁，确保所有房间连通且路径总长度最短，形成自然的迷宫结构。
  • NPC 路径规划：在密集的场景（如城堡、地下城）中，预先生成最小生成树作为 NPC 的移动骨架，确保路径连通性和效率。

#include "prim_algorithm.h"// 应用场景4: 游戏迷宫生成
void gameMazeGeneration(int width, int height) {printf("\n--- 应用4: 游戏迷宫生成 ---\n");int maze_width = 2 * width + 1;int maze_height = 2 * height + 1;int total_cells = width * height;// 创建迷宫数组（初始全部为墙）char **maze = (char**)malloc(maze_height * sizeof(char*));for (int i = 0; i < maze_height; i++) {maze[i] = (char*)malloc(maze_width * sizeof(char));for (int j = 0; j < maze_width; j++) {maze[i][j] = '#';  // '#'表示墙}}// 创建图表示迷宫单元格Graph graph;initGraph(&graph, total_cells);// 添加水平和垂直连接（随机权重）srand(time(NULL));for (int i = 0; i < width; i++) {for (int j = 0; j < height; j++) {int cell_id = i * height + j;// 右邻居if (i + 1 < width) {int right_id = (i + 1) * height + j;int weight = rand() % 100 + 1;addEdge(&graph, cell_id, right_id, weight);}// 下邻居if (j + 1 < height) {int down_id = i * height + (j + 1);int weight = rand() % 100 + 1;addEdge(&graph, cell_id, down_id, weight);}}}// 计算最小生成树int mst_size;Edge *mst = primMST(&graph, &mst_size);// 根据MST打通路径for (int i = 0; i < mst_size; i++) {// 计算单元格坐标int src_x = mst[i].src / height;int src_y = mst[i].src % height;int dest_x = mst[i].dest / height;int dest_y = mst[i].dest % height;// 计算迷宫中的坐标int maze_src_x = 2 * src_x + 1;int maze_src_y = 2 * src_y + 1;int maze_dest_x = 2 * dest_x + 1;int maze_dest_y = 2 * dest_y + 1;// 打通当前单元格maze[maze_src_x][maze_src_y] = ' ';maze[maze_dest_x][maze_dest_y] = ' ';// 打通中间的墙int mid_x = (maze_src_x + maze_dest_x) / 2;int mid_y = (maze_src_y + maze_dest_y) / 2;maze[mid_x][mid_y] = ' ';}// 设置入口和出口maze[1][0] = ' ';  // 入口maze[maze_height - 2][maze_width - 1] = ' ';  // 出口// 打印迷宫printf("游戏迷宫生成结果（%dx%d）:\n", width, height);for (int i = 0; i < maze_height; i++) {for (int j = 0; j < maze_width; j++) {printf("%c", maze[i][j]);}printf("\n");}// 释放内存free(mst);for (int i = 0; i < maze_height; i++) {free(maze[i]);}free(maze);
}    

5. 社交网络与社区分析

• 场景：分析社交网络中用户的紧密连接关系，构建最小成本的信息传播网络。
• 应用：
  • 将用户视为顶点，互动频率或亲密度视为边权，普里姆算法可从核心用户（如意见领袖）出发，逐步连接其他用户，形成最小传播成本的网络，辅助信息扩散策略设计。

#include "prim_algorithm.h"// 应用场景5: 社交网络分析
void socialNetworkAnalysis(int num_users) {printf("\n--- 应用5: 社交网络分析 ---\n");Graph graph;initGraph(&graph, num_users);// 随机生成社交网络连接和互动频率srand(time(NULL));for (int i = 0; i < num_users; i++) {for (int j = i + 1; j < num_users; j++) {if (rand() % 3 == 0) {  // 33%概率有连接int interaction = rand() % 20 + 1;  // 互动频率1-20addEdge(&graph, i, j, interaction);}}}// 计算最小生成树（信息传播最小网络）int mst_size;Edge *mst = primMST(&graph, &mst_size);int total_strength = calculateTotalWeight(mst, mst_size);printf("社交网络分析结果（%d个用户）:\n", num_users);printf("信息传播最小网络强度: %d\n", total_strength);free(mst);
}    

总结

普里姆算法通过 “局部最优选择” 逐步构建全局最优的最小生成树，尤其适合顶点密集、边权复杂的场景。其核心优势在于实现直观、适合邻接矩阵表示的稠密图，广泛应用于网络设计、电路优化、游戏开发等领域。实际应用中，可结合优先队列（如堆）优化顶点选择过程，提升稀疏图场景下的效率。

1.2 克鲁斯卡尔算法

克鲁斯卡尔算法是一种用于求解无向连通加权图的最小生成树（MST）的贪心算法。其核心思想是按边权从小到大的顺序选择边，确保每次选择的边不会形成环，直到包含图中所有顶点。该算法适用于稀疏图（边数较少），时间复杂度为 O(ElogE)，其中 E 为边数。

算法步骤

1. 初始化：

   • 将图中所有边按权值从小到大排序。
   • 初始化一个空的边集合（用于存储 MST）和一个并查集（用于检测环）。

2. 迭代选择边：

   • 从排序后的边列表中取出最小权值的边。
   • 若该边的两个顶点不在同一个连通分量中（通过并查集判断），则将该边加入 MST，并合并这两个顶点所在的连通分量。
   • 否则，跳过该边（避免形成环）。

3. 终止条件：

   • 当 MST 中的边数达到 V−1 条（V 为顶点数）时，算法结束。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 边的结构体，包含起点、终点和权值
struct Edge {int src, dest, weight;
};// 比较函数，用于按权值对边进行排序
bool compareEdges(const Edge& a, const Edge& b) {return a.weight < b.weight;
}// 查找操作，使用路径压缩优化
int find(vector<int>& parent, int i) {if (parent[i] != i)parent[i] = find(parent, parent[i]);return parent[i];
}// 合并操作，使用按秩合并优化
void unionSets(vector<int>& parent, vector<int>& rank, int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot])parent[xroot] = yroot;else if (rank[xroot] > rank[yroot])parent[yroot] = xroot;else {parent[yroot] = xroot;rank[xroot]++;}
}// 克鲁斯卡尔算法实现
vector<Edge> kruskalMST(int V, vector<Edge>& edges) {vector<Edge> result;  // 存储最小生成树的边int e = 0;            // 结果中的边数int i = 0;            // 当前处理的边数// 按权值对边进行排序sort(edges.begin(), edges.end(), compareEdges);// 分配内存用于存储子集vector<int> parent(V);vector<int> rank(V);// 初始化所有点的父节点为自身，秩为0for (int node = 0; node < V; node++) {parent[node] = node;rank[node] = 0;}// 遍历所有排序后的边while (e < V - 1 && i < edges.size()) {Edge next_edge = edges[i++];int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);// 如果包含这条边不会形成环，则加入结果集if (x != y) {result.push_back(next_edge);e++;unionSets(parent, rank, x, y);}}return result;
}int main() {int V = 4;  // 顶点数vector<Edge> edges = {{0, 1, 10},{0, 2, 6},{0, 3, 5},{1, 3, 15},{2, 3, 4}};vector<Edge> mst = kruskalMST(V, edges);cout << "最小生成树的边集:" << endl;for (const Edge& edge : mst) {cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;}return 0;
}

应用场景：

例如：应用克鲁斯卡尔算法写出图像分割与计算机视觉

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <opencv2/opencv.hpp>using namespace std;
using namespace cv;// 边的结构体，包含起点、终点和权值
struct Edge {int src, dest;float weight;bool operator<(const Edge& other) const {return weight < other.weight;}
};// 并查集节点
struct UnionFindNode {int parent;int rank;int size;
};// 并查集操作类
class UnionFind {
private:vector<UnionFindNode> nodes;
public:explicit UnionFind(int size) {nodes.resize(size);for (int i = 0; i < size; i++) {nodes[i].parent = i;nodes[i].rank = 0;nodes[i].size = 1;}}int find(int x) {if (nodes[x].parent != x)nodes[x].parent = find(nodes[x].parent);return nodes[x].parent;}void unite(int x, int y) {int xRoot = find(x);int yRoot = find(y);if (xRoot == yRoot) return;if (nodes[xRoot].rank < nodes[yRoot].rank) {nodes[xRoot].parent = yRoot;nodes[yRoot].size += nodes[xRoot].size;} else {nodes[yRoot].parent = xRoot;nodes[xRoot].size += nodes[yRoot].size;if (nodes[xRoot].rank == nodes[yRoot].rank)nodes[xRoot].rank++;}}int getSize(int x) {return nodes[find(x)].size;}
};// 图像分割类
class ImageSegmentation {
private:Mat image;int width, height;vector<Edge> edges;vector<int> colors;// 计算两个像素之间的相似度（颜色和空间距离）float calculateEdgeWeight(const Vec3b& p1, const Vec3b& p2, int dx, int dy) {float colorDiff = sqrt(pow(p1[0] - p2[0], 2) +pow(p1[1] - p2[1], 2) +pow(p1[2] - p2[2], 2));float spatialDiff = sqrt(dx*dx + dy*dy);return colorDiff * 0.8 + spatialDiff * 0.2; // 加权组合}// 生成图像的图表示void buildGraph() {edges.clear();int idx = 0;for (int y = 0; y < height; y++) {for (int x = 0; x < width; x++) {// 向右的边if (x < width - 1) {Edge e;e.src = y * width + x;e.dest = y * width + (x + 1);e.weight = calculateEdgeWeight(image.at<Vec3b>(y, x),image.at<Vec3b>(y, x + 1),1, 0);edges.push_back(e);}// 向下的边if (y < height - 1) {Edge e;e.src = y * width + x;e.dest = (y + 1) * width + x;e.weight = calculateEdgeWeight(image.at<Vec3b>(y, x),image.at<Vec3b>(y + 1, x),0, 1);edges.push_back(e);}// 右下对角线的边if (x < width - 1 && y < height - 1) {Edge e;e.src = y * width + x;e.dest = (y + 1) * width + (x + 1);e.weight = calculateEdgeWeight(image.at<Vec3b>(y, x),image.at<Vec3b>(y + 1, x + 1),1, 1);edges.push_back(e);}// 左下对角线的边if (x > 0 && y < height - 1) {Edge e;e.src = y * width + x;e.dest = (y + 1) * width + (x - 1);e.weight = calculateEdgeWeight(image.at<Vec3b>(y, x),image.at<Vec3b>(y + 1, x - 1),1, 1);edges.push_back(e);}}}}// 生成随机颜色void generateRandomColors(int numColors) {colors.resize(numColors);for (int i = 0; i < numColors; i++) {colors[i] = (rand() & 0xFF) << 16 | (rand() & 0xFF) << 8  | (rand() & 0xFF);}}public:explicit ImageSegmentation(const Mat& inputImage) : image(inputImage) {width = image.cols;height = image.rows;}// 执行图像分割Mat segment(float threshold = 10.0, int minComponentSize = 50) {buildGraph();sort(edges.begin(), edges.end());int numPixels = width * height;UnionFind uf(numPixels);vector<float> thresholdArray(numPixels, threshold);// 克鲁斯卡尔算法核心for (const Edge& edge : edges) {int a = uf.find(edge.src);int b = uf.find(edge.dest);if (a != b) {if (edge.weight <= thresholdArray[a] && edge.weight <= thresholdArray[b]) {uf.unite(a, b);int newRoot = uf.find(a);thresholdArray[newRoot] = edge.weight + threshold / uf.getSize(newRoot);}}}// 后处理：移除小区域for (const Edge& edge : edges) {int a = uf.find(edge.src);int b = uf.find(edge.dest);if (a != b) {if ((uf.getSize(a) < minComponentSize || uf.getSize(b) < minComponentSize) &&edge.weight <= thresholdArray[a] && edge.weight <= thresholdArray[b]) {uf.unite(a, b);}}}// 创建分割结果图像Mat result = Mat::zeros(height, width, CV_8UC3);vector<int> componentColors(numPixels, -1);int nextColor = 0;generateRandomColors(numPixels);for (int y = 0; y < height; y++) {for (int x = 0; x < width; x++) {int pixelIndex = y * width + x;int component = uf.find(pixelIndex);if (componentColors[component] == -1) {componentColors[component] = nextColor++;}int color = colors[componentColors[component]];result.at<Vec3b>(y, x)[0] = (color >> 16) & 0xFF;result.at<Vec3b>(y, x)[1] = (color >> 8) & 0xFF;result.at<Vec3b>(y, x)[2] = color & 0xFF;}}return result;}
};int main() {// 读取图像Mat image = imread("input.jpg");if (image.empty()) {cout << "无法读取图像!" << endl;return -1;}// 调整图像大小以加快处理速度if (image.cols > 800 || image.rows > 600) {resize(image, image, Size(800, 600));}// 执行图像分割ImageSegmentation seg(image);Mat segmentedImage = seg.segment(15.0, 100);// 显示原图和分割结果imshow("原图", image);imshow("分割结果", segmentedImage);waitKey(0);// 保存结果imwrite("segmented.jpg", segmentedImage);return 0;
}

总结：

对比项	克鲁斯卡尔算法	普里姆算法
算法策略	按边权排序，全局选边，避免环。	从顶点出发，逐步扩展生成树。
时间复杂度	O(ElogE)	O(V2) 或 O(ElogV)
适用场景	稀疏图（边数远小于 V2）。	稠密图（边数接近 V2）。
数据结构依赖	并查集（Union-Find）用于环检测。	优先队列（堆）或邻接矩阵。
实现难度	较复杂（需实现并查集）。	较简单（基于贪心扩展）。
空间复杂度	O(E)（存储所有边）。	O(V2)（邻接矩阵）或 O(E)。

二，最短路径算法

原理：最短路径算法主要解决的是在图中找到从一个节点（源点）到另一个节点（目标点）的路径中，边的权值之和最小的路径。

2.1 Dijkstra 算法（单源最短路径）

适用条件：所有边权为非负的图。
核心思想：贪心策略，逐步扩展已确定最短路径的节点集合。
原理步骤：

1. 初始化：将源点的距离设为 0，其他节点设为无穷大（∞）。
2. 选择节点：从未确定最短路径的节点中选择距离最小的节点 u。
3. 松弛操作：对 u 的所有邻接节点 v，若通过 u 到达 v 的路径更短，则更新 v 的距离。
4. 标记节点：将 u 标记为已确定最短路径，重复步骤 2-3 直到所有节点被标记。

代码示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100  // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大（十六进制，约等于1e9）// 邻接矩阵存储图结构
typedef struct {int vexnum, arcnum;          // 顶点数、边数int arc[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
} MGraph;// 初始化图（邻接矩阵）
void CreateMGraph(MGraph* G) {int i, j, k, w;printf("请输入顶点数和边数（空格分隔）：");scanf_s("%d %d", &G->vexnum, &G->arcnum);// 初始化邻接矩阵为无穷大for (i = 0; i < G->vexnum; i++) {for (j = 0; j < G->vexnum; j++) {G->arc[i][j] = INF;}}// 输入每条边的信息（顶点编号从0开始）printf("请输入每条边的起点、终点、权值（空格分隔）：\n");for (k = 0; k < G->arcnum; k++) {scanf_s("%d %d %d", &i, &j, &w);G->arc[i][j] = w; // 有向图，若为无向图需添加 G->arc[j][i] = w;}
}// 迪杰斯特拉算法：求顶点v0到其余顶点的最短路径
void Dijkstra(MGraph G, int v0, int dist[], int path[]) {int s[MAX_VERTEX]; // s[i]=1表示顶点i的最短路径已确定int i, j, u, min;// 初始化dist和s数组for (i = 0; i < G.vexnum; i++) {dist[i] = G.arc[v0][i]; // 初始距离为v0到i的直接边权s[i] = 0;                // 初始时所有顶点未确定if (G.arc[v0][i] < INF)  // 若v0到i有直接边，记录路径为v0->ipath[i] = v0;elsepath[i] = -1;        // 无直接边时路径标记为-1}s[v0] = 1; // 起点v0的最短路径已确定path[v0] = -1; // 起点无前驱// 遍历其余顶点，寻找最短路径for (i = 1; i < G.vexnum; i++) {min = INF;// 寻找未确定顶点中距离最小的顶点ufor (j = 0; j < G.vexnum; j++) {if (!s[j] && dist[j] < min) {min = dist[j];u = j;}}s[u] = 1; // 标记u为已确定// 以u为中间点，更新其他顶点的最短距离for (j = 0; j < G.vexnum; j++) {if (!s[j] && G.arc[u][j] < INF && dist[u] + G.arc[u][j] < dist[j]) {dist[j] = dist[u] + G.arc[u][j]; // 更新距离path[j] = u;                     // 记录前驱顶点}}}
}// 打印最短路径及距离
void PrintPath(MGraph G, int v0, int dist[], int path[]) {int i, j, k;printf("顶点%d到各顶点的最短距离及路径：\n", v0);for (i = 0; i < G.vexnum; i++) {if (i == v0) continue; // 跳过起点printf("到顶点%d: 距离=%d，路径: %d", i, dist[i], v0);k = i;while (path[k] != -1) { // 逆序追踪路径printf(" -> %d", path[k]);k = path[k];}printf("\n");}
}int main() {MGraph G;int dist[MAX_VERTEX], path[MAX_VERTEX]; // 最短距离和路径数组CreateMGraph(&G); // 初始化图// 执行迪杰斯特拉算法（假设起点为0号顶点）Dijkstra(G, 0, dist, path);// 打印结果PrintPath(G, 0, dist, path);return 0;
}

应用场景：

1. 地图导航与路径规划

• 应用：计算两点间的最短驾驶路线、步行路径或公共交通路线。
• 场景举例：
  • 高德地图、Google Maps 等导航软件中，寻找最快 / 最短行车路线。
  • 物流配送系统中，优化货车的送货路径。
• 特点：道路网络通常以图表示，路段长度 / 行驶时间作为边权（非负）。

• // 地图导航示例
  void mapNavigationExample() {// 构建地图图结构 (节点数, 边)vector<vector<ii>> mapGraph = {{{1, 10}, {2, 15}},  // 节点0连接节点1(距离10)和节点2(距离15){{3, 12}},           // 节点1连接节点3(距离12){{3, 5}},            // 节点2连接节点3(距离5){{4, 8}},            // 节点3连接节点4(距离8){}                   // 节点4没有出边};int startNode = 0;int destinationNode = 4;vector<int> distances = dijkstra(mapGraph, startNode);cout << "地图导航示例:" << endl;cout << "从节点 " << startNode << " 到节点 " << destinationNode << " 的最短距离是: " << distances[destinationNode] << endl;
  }

2. 社交网络与人际关系分析

• 应用：计算用户之间的 “最短连接路径” 或 “社交距离”。
• 场景举例：
  • 微信 / QQ 中查找两个用户之间的共同好友链（如 “A 通过 B 认识 C”）。
  • LinkedIn 中推荐 “二度人脉”（朋友的朋友）。
• 特点：社交网络中的边权可设为 1（表示一度连接），Dijkstra 算法能快速找到最短关系链。

• // 地图导航示例
  void mapNavigationExample() {// 构建地图图结构 (节点数, 边)vector<vector<ii>> mapGraph = {{{1, 10}, {2, 15}},  // 节点0连接节点1(距离10)和节点2(距离15){{3, 12}},           // 节点1连接节点3(距离12){{3, 5}},            // 节点2连接节点3(距离5){{4, 8}},            // 节点3连接节点4(距离8){}                   // 节点4没有出边};int startNode = 0;int destinationNode = 4;vector<int> distances = dijkstra(mapGraph, startNode);cout << "地图导航示例:" << endl;cout << "从节点 " << startNode << " 到节点 " << destinationNode << " 的最短距离是: " << distances[destinationNode] << endl;
  }

3. 计算机网络与路由协议

• 应用：数据包在网络中的最优路径选择。
• 场景举例：
  • 路由器使用 SPF（最短路径优先）算法（如 OSPF 协议）构建路由表。
  • 数据中心内部，优化服务器间的通信路径。
• 特点：网络延迟或带宽作为边权，确保数据包最快到达目的地。

• // 计算机网络路由示例
  void networkRoutingExample() {// 构建网络拓扑图 (节点为路由器, 边权为延迟)vector<vector<ii>> networkGraph = {{{1, 5}, {2, 2}},    // 路由器0到路由器1延迟5ms, 到路由器2延迟2ms{{0, 5}, {3, 7}},    // 路由器1到路由器0延迟5ms, 到路由器3延迟7ms{{0, 2}, {3, 3}},    // 路由器2到路由器0延迟2ms, 到路由器3延迟3ms{{1, 7}, {2, 3}, {4, 4}}, // 路由器3到路由器1延迟7ms, 到路由器2延迟3ms, 到路由器4延迟4ms{{3, 4}}             // 路由器4到路由器3延迟4ms};int sourceRouter = 0;int targetRouter = 4;// 带路径记录的Dijkstra算法int n = networkGraph.size();vector<int> dist(n, INF);vector<int> prev(n, -1);dist[sourceRouter] = 0;priority_queue<ii, vector<ii>, greater<ii>> pq;pq.push({0, sourceRouter});while (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();if (d > dist[u]) continue;for (const auto& edge : networkGraph[u]) {int v = edge.first;int weight = edge.second;if (dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;prev[v] = u;pq.push({dist[v], v});}}}cout << "\n计算机网络路由示例:" << endl;cout << "从路由器 " << sourceRouter << " 到路由器 " << targetRouter << " 的最短路径延迟是: " << dist[targetRouter] << "ms" << endl;vector<int> path = getPath(prev, targetRouter);cout << "数据传输路径: ";for (int i = 0; i < path.size(); i++) {cout << path[i];if (i != path.size() - 1) cout << " -> ";}cout << endl;
  }

4. 游戏开发与路径搜索

• 应用：游戏中 NPC（非玩家角色）的寻路算法。
• 场景举例：
  • 角色扮演游戏（RPG）中，角色绕过障碍物前往目的地。
  • 策略游戏（如《文明》）中，计算部队的最优移动路径。
• 特点：游戏地图通常被离散化为网格或节点图，Dijkstra 算法可找到无障碍物的最短路径。

• // 游戏路径规划示例 (简化的网格地图)
  void gamePathfindingExample() {// 构建游戏地图 (0=可通行, 1=障碍物)vector<vector<int>> grid = {{0, 0, 0, 0, 0},{0, 1, 1, 0, 0},{0, 1, 0, 0, 0},{0, 0, 0, 1, 0},{0, 0, 0, 1, 0}};int rows = grid.size();int cols = grid[0].size();// 将网格转换为图结构vector<vector<ii>> gameGraph(rows * cols);auto nodeId = [&](int x, int y) {return x * cols + y;};vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};for (int x = 0; x < rows; x++) {for (int y = 0; y < cols; y++) {if (grid[x][y] == 1) continue; // 障碍物int u = nodeId(x, y);for (const auto& dir : directions) {int nx = x + dir.first;int ny = y + dir.second;if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 0) {int v = nodeId(nx, ny);gameGraph[u].push_back({v, 1}); // 相邻节点距离为1}}}}int startX = 0, startY = 0;int goalX = 4, goalY = 4;int startNode = nodeId(startX, startY);int goalNode = nodeId(goalX, goalY);// 带路径记录的Dijkstraint n = gameGraph.size();vector<int> dist(n, INF);vector<int> prev(n, -1);dist[startNode] = 0;priority_queue<ii, vector<ii>, greater<ii>> pq;pq.push({0, startNode});while (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();if (d > dist[u]) continue;for (const auto& edge : gameGraph[u]) {int v = edge.first;int weight = edge.second;if (dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;prev[v] = u;pq.push({dist[v], v});}}}cout << "\n游戏路径规划示例:" << endl;cout << "从起点 (" << startX << "," << startY << ") 到终点 (" << goalX << "," << goalY << ") 的最短路径长度是: " << dist[goalNode] << endl;vector<int> path = getPath(prev, goalNode);// 打印路径vector<vector<char>> pathGrid(rows, vector<char>(cols, '.'));for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 1) pathGrid[i][j] = '#';}}for (int node : path) {int x = node / cols;int y = node % cols;pathGrid[x][y] = '*';}// 标记起点和终点pathGrid[startX][startY] = 'S';pathGrid[goalX][goalY] = 'E';cout << "路径可视化:" << endl;for (const auto& row : pathGrid) {for (char c : row) {cout << c << ' ';}cout << endl;}
  }

5. 电力与通信网络优化

• 应用：在电缆、管道等基础设施中寻找最优铺设路径。
• 场景举例：
  • 电力公司规划输电线路，最小化建设成本。
  • 通信运营商铺设光纤网络，连接多个基站。
• 特点：铺设成本、距离等作为边权，确保总开销最小。

6. 资源分配与调度

• 应用：优化资源分配路径，最小化总消耗。
• 场景举例：
  • 云计算中，调度任务到计算节点的最优路径。
  • 供应链管理中，规划货物从仓库到门店的最短运输路线。
• 特点：资源消耗、时间成本等作为边权。

7. 机器人路径规划

• 应用：自主机器人（如扫地机器人、无人机）的路径规划。
• 场景举例：
  • 机器人在仓库中避障并找到货物存放点。
  • 无人机测绘时规划覆盖所有目标点的最短路径。
• 特点：机器人移动的距离、时间或能耗作为边权。

2.2 弗洛伊德算法

弗洛伊德算法（Floyd-Warshall Algorithm）是一种经典的动态规划算法，用于求解图中所有节点对之间的最短路径。其时间复杂度为 O(V3)，适用于节点数较少的稠密图。

示例代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100  // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大（十六进制，约等于1e9）// 邻接矩阵存储图结构
typedef struct {int vexnum, arcnum;          // 顶点数、边数int arc[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
} MGraph;// 初始化图（邻接矩阵）
void CreateMGraph(MGraph* G) {int i, j, k, w;printf("请输入顶点数和边数（空格分隔）：");scanf_s("%d %d", &G->vexnum, &G->arcnum);// 初始化邻接矩阵为无穷大for (i = 0; i < G->vexnum; i++) {for (j = 0; j < G->vexnum; j++) {G->arc[i][j] = INF;if (i == j) G->arc[i][j] = 0; // 顶点到自身距离为0}}// 输入每条边的信息（顶点编号从0开始）printf("请输入每条边的起点、终点、权值（空格分隔）：\n");for (k = 0; k < G->arcnum; k++) {scanf_s("%d %d %d", &i, &j, &w);G->arc[i][j] = w; // 有向图，若为无向图需添加 G->arc[j][i] = w;}
}// 弗洛伊德算法：求任意两点间的最短路径
void Floyd(MGraph G, int dist[MAX_VERTEX][MAX_VERTEX], int path[MAX_VERTEX][MAX_VERTEX]) {int i, j, k;// 初始化距离矩阵和路径矩阵for (i = 0; i < G.vexnum; i++) {for (j = 0; j < G.vexnum; j++) {dist[i][j] = G.arc[i][j]; // 初始距离为直接边权path[i][j] = j;           // 初始路径为i->j（若存在直接边）}}// 三层循环更新最短路径for (k = 0; k < G.vexnum; k++) { // 中间顶点kfor (i = 0; i < G.vexnum; i++) { // 起点ifor (j = 0; j < G.vexnum; j++) { // 终点j// 若经过k的路径更短，则更新dist和pathif (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {dist[i][j] = dist[i][k] + dist[k][j];path[i][j] = path[i][k]; // 记录前驱顶点（可优化为记录路径中间点）}}}}
}// 打印最短路径及距离（简化版，仅输出距离矩阵）
void PrintResult(MGraph G, int dist[MAX_VERTEX][MAX_VERTEX]) {int i, j;printf("最短距离矩阵:\n");for (i = 0; i < G.vexnum; i++) {for (j = 0; j < G.vexnum; j++) {if (dist[i][j] == INF)printf("INF\t");elseprintf("%d\t", dist[i][j]);}printf("\n");}
}int main() {MGraph G;int dist[MAX_VERTEX][MAX_VERTEX], path[MAX_VERTEX][MAX_VERTEX]; // 距离矩阵和路径矩阵CreateMGraph(&G); // 初始化图Floyd(G, dist, path); // 执行弗洛伊德算法PrintResult(G, dist); // 打印最短距离矩阵return 0;
}/*算法思想
动态规划：通过中间顶点 k 逐步优化任意两点 i 和 j之间的最短路径。三层循环：
第一层循环：中间顶点 k（从 0 到 V−1）。
第二层循环：起点 i。
第三层循环：终点 j。
状态转移：若经过中间点 k的路径 i→k→j 更短，则更新 i到 j的最短距离。
*/

应用场景示例：

1. 社交网络分析

• 计算社交网络中用户间的最短关系路径：

// 社交网络中计算用户间最短路径
void socialNetworkAnalysis() {// 假设graph表示用户关系图，边权表示亲密度vector<vector<int>> socialGraph = /* 初始化社交网络图 */;vector<vector<int>> distances = floydWarshall(socialGraph);// 输出用户1到用户5的最短路径长度cout << "用户1到用户5的最短关系路径长度：" << distances[0][4] << endl;
}

2. 地图导航

• 计算城市中任意两点间的最短驾驶距离：

// 地图导航中的路径规划
void mapNavigation() {// 假设roadNetwork表示城市道路网络vector<vector<int>> roadNetwork = /* 初始化道路网络图 */;vector<vector<int>> shortestRoutes = floydWarshall(roadNetwork);// 输出从地点A(索引2)到地点B(索引7)的最短距离cout << "从地点A到地点B的最短距离：" << shortestRoutes[2][7] << "公里" << endl;
}

3. 电路设计

• 计算芯片引脚间的最短连线：

// 电路设计中的引脚连接优化
void circuitDesign() {// 假设pinConnections表示芯片引脚连接图vector<vector<int>> pinConnections = /* 初始化引脚连接图 */;vector<vector<int>> minWiringLength = floydWarshall(pinConnections);// 输出引脚3到引脚9的最短连线长度cout << "引脚3到引脚9的最短连线长度：" << minWiringLength[2][8] << "微米" << endl;
}

4. 游戏开发

• 游戏地图中 NPC 的路径规划：

// 游戏地图中的路径规划
void gamePathfinding() {// 假设gameMap表示游戏地图的可达性图vector<vector<int>> gameMap = /* 初始化游戏地图 */;vector<vector<int>> npcPaths = floydWarshall(gameMap);// 输出NPC从位置(4)到玩家(12)的最短移动步数cout << "NPC到玩家的最短路径步数：" << npcPaths[4][12] << endl;
}

弗洛伊德算法在 C++ 中的实现核心是三层嵌套循环，通过动态规划逐步优化所有节点对之间的路径。在实际应用中，你可以根据具体场景调整图的表示方式和边权值的含义，以适应不同领域的需求。

三.拓扑排序

拓扑排序是对有向无环图（DAG）的节点进行排序的一种算法，其核心思想是将图中的所有节点排成一个线性序列，使得对于图中的任意一条有向边 (u, v)，节点 u 在序列中都出现在节点 v 之前。这种排序方式常用于任务调度、课程安排等依赖关系明确的场景。

原理步骤

1. 入度计算：统计每个节点的入度（即有多少条边指向该节点），入度为 0 的节点表示没有前置依赖。
2. 队列初始化：将所有入度为 0 的节点加入队列。
3. 节点处理：
   • 从队列中取出一个节点并加入排序结果。
   • 移除该节点的所有出边（即减少其所有邻接节点的入度）。
   • 若某个邻接节点的入度变为 0，则将其加入队列。
4. 循环处理：重复步骤 3，直到队列为空。
5. 结果验证：如果排序结果包含所有节点，则排序成功；否则，图中存在环，无法进行拓扑排序。

示例说明代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100  // 最大顶点数// 邻接表边节点
typedef struct ArcNode {int adjvex;          // 邻接点下标struct ArcNode* next; // 指向下一个邻接点
} ArcNode;// 邻接表顶点节点
typedef struct VNode {int data;           // 顶点值int inDegree;       // 顶点入度ArcNode* firstarc;   // 边表头指针
} VNode, AdjList[MAX_VERTEX];// 图结构
typedef struct {AdjList vertices;   // 顶点数组int vexnum, arcnum;  // 顶点数、边数
} ALGraph;// 创建有向图的邻接表
void CreateALGraph(ALGraph* G) {int i, j, k;ArcNode* p;printf("请输入顶点数和边数（空格分隔）: ");scanf_s("%d %d", &G->vexnum, &G->arcnum);// 初始化顶点数组for (i = 0; i < G->vexnum; i++) {G->vertices[i].data = i;        // 顶点值设为0~n-1G->vertices[i].firstarc = NULL; // 边表置空G->vertices[i].inDegree = 0;    // 入度初始化}printf("请输入每条有向边的起点和终点（空格分隔）:\n");for (k = 0; k < G->arcnum; k++) {scanf_s("%d %d", &i, &j);         // 输入边<i,j>// 创建新边节点p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->next = G->vertices[i].firstarc; // 头插法G->vertices[i].firstarc = p;// 更新终点j的入度G->vertices[j].inDegree++;}
}// DFS拓扑排序辅助数组
int visited[MAX_VERTEX];       // 访问标记
int topo_dfs[MAX_VERTEX];     // DFS拓扑序列
int topo_idx = 0;             // 序列下标// 深度优先搜索递归函数（修改为接受指针）
void DFS_TopologicalSort(ALGraph* G, int v) {visited[v] = 1;ArcNode* p = G->vertices[v].firstarc;while (p) {if (!visited[p->adjvex]) {DFS_TopologicalSort(G, p->adjvex);}p = p->next;}topo_dfs[topo_idx++] = G->vertices[v].data; // 逆序记录
}// 基于DFS的拓扑排序（修改为接受指针）
void TopologicalSort_DFS(ALGraph* G) {int i;// 初始化访问标记for (i = 0; i < G->vexnum; i++) {visited[i] = 0;}topo_idx = 0;// 对每个未访问顶点调用DFSfor (i = 0; i < G->vexnum; i++) {if (!visited[i]) {DFS_TopologicalSort(G, i);}}// 输出DFS拓扑排序结果（需反转）printf("DFS拓扑排序结果: ");for (i = topo_idx - 1; i >= 0; i--) {printf("%d ", topo_dfs[i]);}printf("\n");
}// 基于Kahn算法的拓扑排序（修改为接受指针）
void TopologicalSort_Kahn(ALGraph* G) {int inDegree[MAX_VERTEX];     // 临时入度数组int queue[MAX_VERTEX];        // 队列int front = 0, rear = 0;      // 队列头尾指针int count = 0;                // 已排序顶点数// 复制入度数组for (int i = 0; i < G->vexnum; i++) {inDegree[i] = G->vertices[i].inDegree;}// 将入度为0的顶点入队for (int i = 0; i < G->vexnum; i++) {if (inDegree[i] == 0) {queue[rear++] = i;}}printf("Kahn算法拓扑排序结果: ");while (front < rear) {int v = queue[front++];printf("%d ", G->vertices[v].data);count++;// 遍历v的所有邻接点ArcNode* p = G->vertices[v].firstarc;while (p) {int adjvex = p->adjvex;if (--inDegree[adjvex] == 0) {queue[rear++] = adjvex;}p = p->next;}}// 检查是否存在环if (count < G->vexnum) {printf("\n图中存在环，无法完成拓扑排序！");}printf("\n");
}int main() {ALGraph G;// 创建图CreateALGraph(&G);// 执行两种拓扑排序算法（参数类型已匹配）printf("\n拓扑排序结果：\n");TopologicalSort_DFS(&G);TopologicalSort_Kahn(&G);return 0;
}

通过拓扑排序，可以高效地处理有向无环图中的依赖关系，确保所有任务或节点按正确顺序执行。

应用场景：

1.任务调度与项目管理

• 场景：在软件开发或工程项目中，任务之间存在依赖关系（如 “任务 B 必须在任务 A 完成后才能开始”）。
• 应用：通过拓扑排序确定任务的执行顺序，确保所有前置条件被满足。
• 示例：
  • 构建系统（如 Makefile）确定文件编译顺序。
  • 敏捷开发中安排用户故事的优先级。

2. 课程安排与学习路径规划

• 场景：课程之间存在先修关系（如 “必须先学习微积分才能学习线性代数”）。
• 应用：生成满足所有先修条件的课程表。
• 示例：
  • 大学课程的排课系统。
  • 在线学习平台的学习路径推荐（如 Coursera、Udemy）。

3. 编译依赖解析

• 场景：在软件开发中，模块或库之间存在依赖关系。
• 应用：确定编译顺序，避免因依赖缺失导致的编译错误。
• 示例：
  • Maven、Gradle 等构建工具解析项目依赖。
  • Linux 包管理器（如 apt、yum）安装软件时处理依赖链。

4. 数据流与管道处理

• 场景：数据在多个处理阶段之间流动，每个阶段依赖前一个阶段的输出。
• 应用：优化数据处理流程，确保数据按正确顺序传递。
• 示例：
  • 机器学习中的数据预处理管道。
  • 大数据处理框架（如 Hadoop、Spark）中的任务调度。

5. 事件驱动系统

• 场景：系统中事件之间存在触发关系（如 “事件 B 必须在事件 A 发生后才能触发”）。
• 应用：确定事件处理顺序，避免逻辑错误。
• 示例：
  • 游戏引擎中的事件处理链。
  • 响应式编程中的数据流排序（如 RxJava、RxJS）。

6. 电路设计与硬件验证

• 场景：数字电路中信号传播路径存在依赖关系。
• 应用：验证电路时序，确保信号按预期顺序到达。
• 示例：
  • FPGA/ASIC 设计中的逻辑综合与布局。
  • 硬件描述语言（如 Verilog、VHDL）中的模块连接验证。

7. 数据库事务调度

• 场景：数据库事务之间存在依赖关系（如事务 B 需要读取事务 A 的写入结果）。
• 应用：生成可串行化的事务执行顺序，保证数据一致性。
• 示例：
  • 分布式数据库中的并发控制。
  • 数据库备份与恢复中的操作顺序。

8. 版本控制与发布管理

• 场景：软件版本之间存在依赖关系（如 “版本 2.0 依赖版本 1.5 的功能”）。
• 应用：确定版本发布顺序，管理分支合并。
• 示例：
  • Git 中的提交历史可视化与合并冲突解决。
  • 持续集成 / 持续部署（CI/CD）流水线中的版本发布流程。

四.关键路径

关键路径（Critical Path）是项目管理和图论中的重要概念，用于确定项目中从起点到终点的最长路径，该路径上的活动决定了项目的最短完成时间。关键路径算法主要基于 有向无环图（DAG） 和 边表示活动（AOE 网） 的模型，核心目标是找到影响项目工期的关键活动和路径。以下是其算法原理的详细说明：

1、基本概念

1. AOE 网（Activity On Edge Network）
   用有向无环图表示项目流程，其中：

   • 顶点（事件）：表示一个或多个活动的结束或开始（如 “阶段任务完成”）。
   • 边（活动）：表示具体的任务，边上的权值表示活动持续时间（如 “编码任务需 3 天”）。
   • 唯一的入度为 0 的顶点是起点（源点），唯一的出度为 0 的顶点是终点（汇点）。

2. 关键路径
   从源点到汇点的所有路径中，路径权值之和最大的路径，其长度决定了项目的最短完成时间。关键路径上的活动称为关键活动，若关键活动延迟，整个项目工期将延长。

2、算法核心步骤

关键路径算法基于以下四个核心参数的计算，需结合拓扑排序实现：

1. 拓扑排序（Topological Sorting）

• 作用：确保图中无环，并确定顶点的处理顺序（正序和逆序）。
• 过程：
  • 从图中选择一个入度为 0 的顶点，输出并删除该顶点及其所有出边。
  • 重复直至所有顶点输出（若无法完成，说明图中有环，无关键路径）。
• 结果：得到顶点的拓扑序列（如 v1​,v2​,…,vn​）。

2. 计算事件最早发生时间 ve(vi​)

• 定义：事件 vi​ 最早可以发生的时间，即从源点到 vi​ 的最长路径长度。
• 计算方式（正序遍历拓扑序列）：ve(源点)=0ve(vi​)=maxvj​∈前驱顶点​{ve(vj​)+边 vj​→vi​ 的权值}
  • 每个事件的最早发生时间由其所有前驱事件的最早发生时间加上对应活动时间的最大值决定（确保所有前驱活动完成后，当前事件才能发生）。

3. 计算事件最晚发生时间 vl(vi​)

• 定义：在不延误项目总工期的前提下，事件 vi​ 最晚必须发生的时间。
• 计算方式（逆序遍历拓扑序列，从汇点开始）：vl(汇点)=ve(汇点)vl(vi​)=minvj​∈后继顶点​{vl(vj​)−边 vi​→vj​ 的权值}
  • 每个事件的最晚发生时间由其后继事件的最晚发生时间减去对应活动时间的最小值决定（确保后继活动有足够时间完成）。

4. 计算活动的最早开始时间 e(ak​) 和最晚开始时间 l(ak​)

• 设活动 ak​ 对应边 vi​→vj​，权值为 wi,j​，则：

  • 最早开始时间：e(ak​)=ve(vi​)
    （事件 vi​ 最早发生后，活动 ak​ 才能开始）。
  • 最晚开始时间：l(ak​)=vl(vj​)−wi,j​
    （事件 vj​ 最晚发生前，活动 ak​ 必须完成，故倒推最晚开始时间）。

• 关键活动判定：若 l(ak​)=e(ak​)，则 ak​ 为关键活动（无时间余量，延迟会影响总工期）。

3、算法流程总结

1. 拓扑排序验证图无环，并获取拓扑序列。
2. 正序计算所有事件的最早发生时间 ve(vi​)。
3. 逆序计算所有事件的最晚发生时间 vl(vi​)。
4. 遍历所有活动，计算 e(ak​) 和 l(ak​)，筛选出 l(ak​)=e(ak​) 的关键活动。
5. 关键活动构成的路径即为关键路径（可能存在多条）。

4、算法特点与应用

• 时间复杂度：O(V+E)，其中 V 为顶点数，E 为边数（拓扑排序和两次遍历均为线性时间）。

• 应用场景：

  • 项目管理中的工期规划、资源调度。
  • 任务调度优化，识别瓶颈环节。
  • 集成电路设计中的路径延迟分析。

• 注意事项：

  • 关键路径可能不唯一，需同时优化多条路径上的活动。
  • 非关键活动有时间余量（松弛时间），可灵活调整资源分配。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX 100  // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大// 邻接表边节点（带权值）
typedef struct ArcNode {int adjvex;          // 邻接点下标int weight;          // 边权值（活动持续时间）struct ArcNode* next; // 指向下一个邻接点
} ArcNode;// 邻接表顶点节点
typedef struct VNode {int data;           // 顶点值int inDegree;       // 顶点入度ArcNode* firstarc;   // 边表头指针
} VNode, AdjList[MAX_VERTEX];// 图结构
typedef struct {AdjList vertices;   // 顶点数组int vexnum, arcnum;  // 顶点数、边数
} ALGraph;// 创建有向图的邻接表
void CreateALGraph(ALGraph* G) {int i, j, k, w;ArcNode* p;printf("请输入顶点数和边数（空格分隔）: ");scanf_s("%d %d", &G->vexnum, &G->arcnum);// 初始化顶点数组for (i = 0; i < G->vexnum; i++) {G->vertices[i].data = i;        // 顶点值设为0~n-1G->vertices[i].firstarc = NULL; // 边表置空G->vertices[i].inDegree = 0;    // 入度初始化}printf("请输入每条有向边的起点、终点和权值（空格分隔）:\n");for (k = 0; k < G->arcnum; k++) {scanf_s("%d %d %d", &i, &j, &w);  // 输入边<i,j>及权值// 创建新边节点p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->weight = w;p->next = G->vertices[i].firstarc; // 头插法G->vertices[i].firstarc = p;// 更新终点j的入度G->vertices[j].inDegree++;}
}// 拓扑排序并计算最早开始时间VE
int TopologicalSort(ALGraph* G, int topo[]) {int inDegree[MAX_VERTEX];     // 临时入度数组int queue[MAX_VERTEX];        // 队列int front = 0, rear = 0;      // 队列头尾指针int count = 0;                // 已排序顶点数int i;// 复制入度数组for (i = 0; i < G->vexnum; i++) {inDegree[i] = G->vertices[i].inDegree;}// 将入度为0的顶点入队for (i = 0; i < G->vexnum; i++) {if (inDegree[i] == 0) {queue[rear++] = i;}}// 处理队列while (front < rear) {int v = queue[front++];topo[count++] = v;        // 记录拓扑序列// 遍历v的所有邻接点ArcNode* p = G->vertices[v].firstarc;while (p) {int adjvex = p->adjvex;if (--inDegree[adjvex] == 0) {queue[rear++] = adjvex;}p = p->next;}}// 检查是否存在环if (count < G->vexnum) {printf("图中存在环，无法进行关键路径计算！\n");return 0;}return 1;
}// 计算关键路径
void CriticalPath(ALGraph* G) {int topo[MAX_VERTEX];        // 存储拓扑序列int ve[MAX_VERTEX] = { 0 };    // 事件最早开始时间int vl[MAX_VERTEX];          // 事件最晚开始时间int i, j, k;ArcNode* p;// 步骤1: 拓扑排序if (!TopologicalSort(G, topo)) {return;}// 步骤2: 计算最早开始时间vefor (i = 0; i < G->vexnum; i++) {k = topo[i];p = G->vertices[k].firstarc;while (p) {j = p->adjvex;if (ve[j] < ve[k] + p->weight) {ve[j] = ve[k] + p->weight;}p = p->next;}}// 步骤3: 初始化最晚开始时间vl为项目总工期for (i = 0; i < G->vexnum; i++) {vl[i] = ve[G->vexnum - 1]; // 项目总工期}// 步骤4: 按逆拓扑顺序计算最晚开始时间vlfor (i = G->vexnum - 1; i >= 0; i--) {k = topo[i];p = G->vertices[k].firstarc;while (p) {j = p->adjvex;if (vl[k] > vl[j] - p->weight) {vl[k] = vl[j] - p->weight;}p = p->next;}}// 步骤5: 计算关键活动printf("关键活动为: ");for (i = 0; i < G->vexnum; i++) {p = G->vertices[i].firstarc;while (p) {j = p->adjvex;int e = ve[i];           // 活动最早开始时间int l = vl[j] - p->weight; // 活动最晚开始时间if (e == l) {            // 关键活动printf("(%d->%d) ", i, j);}p = p->next;}}printf("\n");// 输出项目总工期printf("项目总工期为: %d\n", ve[G->vexnum - 1]);
}int main() {ALGraph G;// 创建图CreateALGraph(&G);// 计算关键路径printf("\n关键路径计算结果：\n");CriticalPath(&G);return 0;
}