C语言-数据结构 有向图拓扑排序TopologicalSort（邻接表存储）

ops/2024/10/20 3:21:36/

        拓扑排序算法的实现还是比较简单的，我们需要用到一个顺序栈辅助，采用邻接表进行存储，顶点结点存储入度、顶点信息、指向邻接结点的指针，算法过程是：我们先将入度为0的顶点入栈，然后弹出栈顶结点，记录结点个数的count+1，然后遍历所有邻接结点将其入度都减1，如果有入度为0的顶点那么就进栈，当栈不为空就继续循环，最后通过判断弹出栈的元素个数count是否小于全部顶点数，如果小于说明有环，否则无环（即构成拓扑排序）。注意：拓扑排序的情况在邻接表确定的情况下是唯一的。看文字理解确实有点费劲，不过这个实现的代码不难，如果你理解了栈的情况下，那么直接跟着TopologicalSort代码走一遍很快就能领悟到拓扑排序的奥妙！

下面我们将创建一个有向无环图和一个有向有环图

有向无环图如下：

        d6763b7371eb46aeb833bc0a6e510754.png

代码中我们使用头插法进行创建有向无环图邻接表：

#define MAXVEX 8    // 最大顶点数
typedef char VertexType;  // 顶点类型，使用字符表示
typedef int EdgeType;     // 边上的权值类型，使用整数表示
// 边表结点
typedef struct EdgeNode {int adjvex;         // 顶点下标，表示该边的终点struct EdgeNode* next;  // 指向下一条边的指针
} EdgeNode;// 顶点结点
typedef struct VertexNode {int in;VertexType data;     // 顶点数据EdgeNode* first;     // 指向该顶点的第一条边
} VertexNode, AdjList[MAXVEX];// 图的邻接表表示
typedef struct {AdjList adjList;    // 顶点数组int numNodes;       // 图的顶点数int numEdges;       // 图的边数
} GraphAdjList;//有向无环图邻接表创建
void CreateALGraphNotEncircle(GraphAdjList* G) {int i, j;EdgeNode* e = NULL;char str[] = "ABCDEFGH"; // 顶点数据// 初始化邻接表for (i = 0; i < G->numNodes; i++) {G->adjList[i].data = str[i]; // 设置顶点数据G->adjList[i].first = NULL;  // 边表初始化为空}G->adjList[0].in = 1;G->adjList[1].in = 1;G->adjList[2].in = 1;G->adjList[3].in = 1;G->adjList[4].in = 3;G->adjList[5].in = 0;G->adjList[6].in = 2;G->adjList[7].in = 1;// 添加边 A->Be = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 1; // 邻接顶点序号为Be->next = G->adjList[0].first; // 插入到邻接表的第一个位置G->adjList[0].first = e;// 添加边 B->C->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[1].first;G->adjList[1].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 2; // 邻接顶点序号为Ce->next = G->adjList[1].first;G->adjList[1].first = e;// 添加边 C->De = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 3; // 邻接顶点序号为De->next = G->adjList[2].first;G->adjList[2].first = e;// 添加边 D->He = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 7; // 邻接顶点序号为He->next = G->adjList[3].first;G->adjList[3].first = e;// 添加边 F->A->E->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 0; // 邻接顶点序号为Ae->next = G->adjList[5].first;G->adjList[5].first = e;// 添加边 G->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[6].first;G->adjList[6].first = e;// 添加边 H->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[7].first;G->adjList[7].first = e;// 打印邻接表（字母）和入度EdgeNode* p = NULL;printf("边结点按邻接顶点字母打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%c", G->adjList[p->adjvex].data); // 打印邻接顶点字母p = p->next;}printf("\n");}// 打印邻接表（下标）和入度printf("\n边结点按邻接下标打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%d", p->adjvex); // 打印邻接顶点下标p = p->next;}printf("\n");}
}

293e527c7a0e4844ab67b0cddd0a044f.png

        

        有向有环图如下：

52ca7d4673f2431daf71d429b3b21aee.png

代码中我们使用头插法进行创建有向有环图邻接表：

#define MAXVEX 8    // 最大顶点数
typedef char VertexType;  // 顶点类型，使用字符表示
typedef int EdgeType;     // 边上的权值类型，使用整数表示
// 边表结点
typedef struct EdgeNode {int adjvex;         // 顶点下标，表示该边的终点struct EdgeNode* next;  // 指向下一条边的指针
} EdgeNode;// 顶点结点
typedef struct VertexNode {int in;VertexType data;     // 顶点数据EdgeNode* first;     // 指向该顶点的第一条边
} VertexNode, AdjList[MAXVEX];// 图的邻接表表示
typedef struct {AdjList adjList;    // 顶点数组int numNodes;       // 图的顶点数int numEdges;       // 图的边数
} GraphAdjList;//有向有环图邻接表创建
void CreateALGraphHaveEncircle(GraphAdjList* G) {int i, j;EdgeNode* e = NULL;char str[] = "ABCDEFGH"; // 顶点数据// 初始化邻接表for (i = 0; i < G->numNodes; i++) {G->adjList[i].data = str[i]; // 设置顶点数据G->adjList[i].first = NULL;  // 边表初始化为空}G->adjList[0].in = 1;G->adjList[1].in = 1;G->adjList[2].in = 1;G->adjList[3].in = 1;G->adjList[4].in = 3;G->adjList[5].in = 1;G->adjList[6].in = 2;G->adjList[7].in = 1;// 添加边 A->Be = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 1; // 邻接顶点序号为Be->next = G->adjList[0].first; // 插入到邻接表的第一个位置G->adjList[0].first = e;// 添加边 B->C->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[1].first;G->adjList[1].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 2; // 邻接顶点序号为Ce->next = G->adjList[1].first;G->adjList[1].first = e;// 添加边 C->De = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 3; // 邻接顶点序号为De->next = G->adjList[2].first;G->adjList[2].first = e;// 添加边 D->He = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 7; // 邻接顶点序号为He->next = G->adjList[3].first;G->adjList[3].first = e;// 添加边 F->A->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 0; // 邻接顶点序号为Ae->next = G->adjList[5].first;G->adjList[5].first = e;// 添加边 G->E->Fe = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 5; // 邻接顶点序号为Fe->next = G->adjList[6].first;G->adjList[6].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[6].first;G->adjList[6].first = e;// 添加边 H->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[7].first;G->adjList[7].first = e;// 打印邻接表（字母）和入度EdgeNode* p = NULL;printf("边结点按邻接顶点字母打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%c", G->adjList[p->adjvex].data); // 打印邻接顶点字母p = p->next;}printf("\n");}// 打印邻接表（下标）和入度printf("\n边结点按邻接下标打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%d", p->adjvex); // 打印邻接顶点下标p = p->next;}printf("\n");}
}

ed961009ec2d4e2aa72f7a1fd78dbd7f.png

拓扑排序（TopologicalSort）算法，里面包括顺序栈的实现代码非常简洁：

int TopologicalSort(GraphAdjList GL) {EdgeNode* e;           // 边节点指针，用于遍历邻接表中的边int i, k, gettop;      // 迭代变量和临时变量int top = 0;           // 栈顶指针，初始值为0int count = 0;         // 已输出的节点计数int* stack;            // 存储拓扑排序的栈stack = (int*)malloc(sizeof(int) * MAXVEX); // 动态分配栈空间// 遍历所有节点，将入度为0的节点入栈for (i = 0; i < GL.numNodes; i++) {if (0 == GL.adjList[i].in) {stack[++top] = i; // 入栈，并更新栈顶指针}}printf("\n拓扑排序序列为:\n");// 当栈不为空时，进行拓扑排序while (top != 0) {gettop = stack[top--]; // 出栈操作，获取栈顶元素，并更新栈顶指针printf("%c -> ", GL.adjList[gettop].data); // 打印当前节点的值count++; // 已处理节点计数器加1// 遍历当前节点的所有邻接节点for (e = GL.adjList[gettop].first; e; e = e->next) {k = e->adjvex; // 获取邻接节点的索引if (!(--GL.adjList[k].in)) { // 将邻接节点的入度减1，并检查是否变为0stack[++top] = k; // 如果入度为0，将邻接节点入栈}}}// 如果已处理的节点数小于图中节点总数，说明存在环if (count < GL.numNodes) {return FALSE; // 拓扑排序失败}return TRUE; // 拓扑排序成功
}

完整代码（有向无环图、有环图的邻接表创建、TopologicalSort算法）

#include<stdio.h>
#include<stdlib.h>#define MAXVEX 8    // 最大顶点数
#define TRUE 1 
#define FALSE 0typedef char VertexType;  // 顶点类型，使用字符表示
typedef int EdgeType;     // 边上的权值类型，使用整数表示
typedef int Boolean;      // 布尔类型// 边表结点
typedef struct EdgeNode {int adjvex;         // 顶点下标，表示该边的终点struct EdgeNode* next;  // 指向下一条边的指针
} EdgeNode;// 顶点结点
typedef struct VertexNode {int in;VertexType data;     // 顶点数据EdgeNode* first;     // 指向该顶点的第一条边
} VertexNode, AdjList[MAXVEX];// 图的邻接表表示
typedef struct {AdjList adjList;    // 顶点数组int numNodes;       // 图的顶点数int numEdges;       // 图的边数
} GraphAdjList;//有向无环图邻接表创建
void CreateALGraphNotEncircle(GraphAdjList* G) {int i, j;EdgeNode* e = NULL;char str[] = "ABCDEFGH"; // 顶点数据// 初始化邻接表for (i = 0; i < G->numNodes; i++) {G->adjList[i].data = str[i]; // 设置顶点数据G->adjList[i].first = NULL;  // 边表初始化为空}G->adjList[0].in = 1;G->adjList[1].in = 1;G->adjList[2].in = 1;G->adjList[3].in = 1;G->adjList[4].in = 3;G->adjList[5].in = 0;G->adjList[6].in = 2;G->adjList[7].in = 1;// 添加边 A->Be = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 1; // 邻接顶点序号为Be->next = G->adjList[0].first; // 插入到邻接表的第一个位置G->adjList[0].first = e;// 添加边 B->C->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[1].first;G->adjList[1].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 2; // 邻接顶点序号为Ce->next = G->adjList[1].first;G->adjList[1].first = e;// 添加边 C->De = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 3; // 邻接顶点序号为De->next = G->adjList[2].first;G->adjList[2].first = e;// 添加边 D->He = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 7; // 邻接顶点序号为He->next = G->adjList[3].first;G->adjList[3].first = e;// 添加边 F->A->E->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 0; // 邻接顶点序号为Ae->next = G->adjList[5].first;G->adjList[5].first = e;// 添加边 G->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[6].first;G->adjList[6].first = e;// 添加边 H->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[7].first;G->adjList[7].first = e;// 打印邻接表（字母）和入度EdgeNode* p = NULL;printf("边结点按邻接顶点字母打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%c", G->adjList[p->adjvex].data); // 打印邻接顶点字母p = p->next;}printf("\n");}// 打印邻接表（下标）和入度printf("\n边结点按邻接下标打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%d", p->adjvex); // 打印邻接顶点下标p = p->next;}printf("\n");}
}//有向有环图邻接表创建
void CreateALGraphHaveEncircle(GraphAdjList* G) {int i, j;EdgeNode* e = NULL;char str[] = "ABCDEFGH"; // 顶点数据// 初始化邻接表for (i = 0; i < G->numNodes; i++) {G->adjList[i].data = str[i]; // 设置顶点数据G->adjList[i].first = NULL;  // 边表初始化为空}G->adjList[0].in = 1;G->adjList[1].in = 1;G->adjList[2].in = 1;G->adjList[3].in = 1;G->adjList[4].in = 3;G->adjList[5].in = 1;G->adjList[6].in = 2;G->adjList[7].in = 1;// 添加边 A->Be = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 1; // 邻接顶点序号为Be->next = G->adjList[0].first; // 插入到邻接表的第一个位置G->adjList[0].first = e;// 添加边 B->C->Ge = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 6; // 邻接顶点序号为Ge->next = G->adjList[1].first;G->adjList[1].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 2; // 邻接顶点序号为Ce->next = G->adjList[1].first;G->adjList[1].first = e;// 添加边 C->De = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 3; // 邻接顶点序号为De->next = G->adjList[2].first;G->adjList[2].first = e;// 添加边 D->He = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 7; // 邻接顶点序号为He->next = G->adjList[3].first;G->adjList[3].first = e;// 添加边 F->A->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[5].first;G->adjList[5].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 0; // 邻接顶点序号为Ae->next = G->adjList[5].first;G->adjList[5].first = e;// 添加边 G->E->Fe = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 5; // 邻接顶点序号为Fe->next = G->adjList[6].first;G->adjList[6].first = e;e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[6].first;G->adjList[6].first = e;// 添加边 H->Ee = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = 4; // 邻接顶点序号为Ee->next = G->adjList[7].first;G->adjList[7].first = e;// 打印邻接表（字母）和入度EdgeNode* p = NULL;printf("边结点按邻接顶点字母打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%c", G->adjList[p->adjvex].data); // 打印邻接顶点字母p = p->next;}printf("\n");}// 打印邻接表（下标）和入度printf("\n边结点按邻接下标打印 (入度):\n");for (i = 0; i < G->numNodes; i++) {printf("%c (入度: %d)", G->adjList[i].data, G->adjList[i].in);p = G->adjList[i].first;while (p != NULL) {printf("->%d", p->adjvex); // 打印邻接顶点下标p = p->next;}printf("\n");}
}int TopologicalSort(GraphAdjList GL) {EdgeNode* e;           // 边节点指针，用于遍历邻接表中的边int i, k, gettop;      // 迭代变量和临时变量int top = 0;           // 栈顶指针，初始值为0int count = 0;         // 已输出的节点计数int* stack;            // 存储拓扑排序的栈stack = (int*)malloc(sizeof(int) * MAXVEX); // 动态分配栈空间// 遍历所有节点，将入度为0的节点入栈for (i = 0; i < GL.numNodes; i++) {if (0 == GL.adjList[i].in) {stack[++top] = i; // 入栈，并更新栈顶指针}}printf("\n拓扑排序序列为:\n");// 当栈不为空时，进行拓扑排序while (top != 0) {gettop = stack[top--]; // 出栈操作，获取栈顶元素，并更新栈顶指针printf("%c -> ", GL.adjList[gettop].data); // 打印当前节点的值count++; // 已处理节点计数器加1// 遍历当前节点的所有邻接节点for (e = GL.adjList[gettop].first; e; e = e->next) {k = e->adjvex; // 获取邻接节点的索引if (!(--GL.adjList[k].in)) { // 将邻接节点的入度减1，并检查是否变为0stack[++top] = k; // 如果入度为0，将邻接节点入栈}}}// 如果已处理的节点数小于图中节点总数，说明存在环if (count < GL.numNodes) {return FALSE; // 拓扑排序失败}return TRUE; // 拓扑排序成功
}int main() {GraphAdjList GL;GL.numNodes = MAXVEX;        // 设置顶点数//情况1有向无环图printf("测试有向无环图是否构成拓扑排序\n\n");CreateALGraphNotEncircle(&GL);if (TopologicalSort(GL)) {printf("\n能构成拓扑排序,图中无环\n");}else {printf("\n不能构成拓扑排序,图中有环\n");}printf("\n");//情况2有向有环图printf("测试有向有环图是否构成拓扑排序\n\n");CreateALGraphHaveEncircle(&GL);if (TopologicalSort(GL)) {printf("\n能构成拓扑排序,图中无环\n");}else {printf("\n不能构成拓扑排序,图中有环\n");}return 0;
}

运行结果：

有向无环图

ee7dd2f22d7c4bb78fb51476cf1f07f9.png

有向有环图（A->B->G->F是环）

c508b76c97c448eea47463546a49fd41.png

b2dd2e7a7b1544c68983f08af08cbfea.png

 


http://www.ppmy.cn/ops/111016.html

相关文章

Android 蓝牙服务启动

Android 蓝牙服务启动

蓝牙是Android设备中非常常见的一个feature&#xff0c;设备厂家可以用BT来做RC、连接音箱、设备本身做Sink等常见功能。如果一些设备不需要BT功能&#xff0c;Android也可以通过配置来disable此模块&#xff0c;方便厂家为自己的设备做客制化。APP操作设备的蓝牙功能&#xff…
阅读更多...
Python | Leetcode Python题解之第400题第N位数字

Python | Leetcode Python题解之第400题第N位数字

题目&#xff1a; 题解&#xff1a; class Solution:def findNthDigit(self, n: int) -> int:d, count 1, 9while n > d * count:n - d * countd 1count * 10index n - 1start 10 ** (d - 1)num start index // ddigitIndex index % dreturn num // 10 ** (d - d…
阅读更多...
php 实现JWT

php 实现JWT

在 PHP 中&#xff0c;JSON Web Token (JWT) 是一种开放标准 (RFC 7519) 用于在各方之间作为 JSON 对象安全地传输信息。JWT 通常用于身份验证系统&#xff0c;如 OAuth2 或基于令牌的身份验证。 以下是一个基本的 PHP 实现 JWT 生成和验证的代码示例。 JWT 的组成部分 JWT …
阅读更多...
【论文阅读】视觉分割新SOTA: Segment Anything（SAM）

【论文阅读】视觉分割新SOTA: Segment Anything（SAM）

导言 随着基于对比文本—图像对的预训练&#xff08;CLIP&#xff09;方法或者模型、聊天生成预训练转换器&#xff08;ChatGPT&#xff09;、生成预训练转换器-4&#xff08;GPT-4&#xff09;等基础大模型的出现&#xff0c;通用人工智能&#xff08; AGI&#xff09;的研究…
阅读更多...
Kafka 基于SASL/SCRAM动态认证部署，kafka加账号密码登录部署

Kafka 基于SASL/SCRAM动态认证部署，kafka加账号密码登录部署

文章目录 前言下载 kafka安装启动zookeeper添加账号密码 启动kafka修改kafka配置文件增加jaas授权文件修改启动文件&#xff0c;启动kafka检查是否部署成功 offset explore 连接 前言 其实挺简单的几个配置文件&#xff0c;问大模型一直没说到点上&#xff0c;绕晕了。SASL/SC…
阅读更多...
LeetCode题练习与总结：基本计算器 Ⅱ--227

LeetCode题练习与总结：基本计算器 Ⅱ--227

一、题目描述 给你一个字符串表达式 s &#xff0c;请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。 你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。 注意&#xff1a;不允许使用任何将字符串作为数学表达式计算…
阅读更多...
DesignPattern设计模式

DesignPattern设计模式

1 前言 1.1 内容概要 理解使用设计模式的目的掌握软件设计的SOLID原则理解单例的思想&#xff0c;并且能够设计一个单例理解工厂设计模式的思想&#xff0c;能够设计简单工厂&#xff0c;理解工厂方法了解建造者模式的思想&#xff0c;掌握其代码风格理解代理设计模式的思想&a…
阅读更多...
代码随想录训练营 Day60打卡 图论part10 SPFA算法 Bellman-Ford 之判断负权回路 Bellman-Ford 之单源有限最短路

代码随想录训练营 Day60打卡 图论part10 SPFA算法 Bellman-Ford 之判断负权回路 Bellman-Ford 之单源有限最短路

代码随想录训练营 Day60打卡 图论part10 一、Bellman_ford 队列优化算法&#xff08;又名SPFA&#xff09; 例题&#xff1a;卡码94. 城市间货物运输 I 题目描述 某国为促进城市间经济交流&#xff0c;决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市&#xff0c;通过…
阅读更多...
最新文章

Copyright @ 2022~2023