拓扑排序 古城微笑少年丶 2021-12-05 14:53 262阅读 0赞 ### 拓扑排序 ### * 源代码 * 测试1 * * 输入 * 输出 * 测试2 * * 输入 * 输出 # 源代码 # #include<bits/stdc++.h> using namespace std; const int maxn = 1e2; bool g[maxn][maxn]={ false};//利用邻接矩阵表示无权有向图 int n;//表示顶点个数,从1开始编号 int top[maxn];//拓扑序列 /*拓扑排序 true:能够进行拓扑排序 false:存在环 */ bool topSort(){ int stack[maxn],p=0;//用数组来模拟栈,p代表栈顶指针,指向栈顶元素的下一位置 int index = 0;//代表top的下标 int in[maxn];//存放顶点的入度数 for(int i=1;i<=n;i++) { int inDdgree=0;//计算顶点的入度 for(int j=1;j<=n;j++){ if(g[j][i])inDdgree++; } in[i]=inDdgree; if(!inDdgree)stack[p++]=i; } int v;// 出栈顶点 while(p){ v = stack[--p]; top[index++]=v; for(int i=1;i<=n;i++){ if(g[v][i]){ in[i]--; if(!in[i])stack[p++]=i; } } } return n==index; } int main(){ int m; int a,b; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); g[a+1][b+1]=true; } if(topSort()){ for(int i=0;i<n;i++){ printf("%d ",top[i]); } }else{ printf("该图存在负环"); } } # 测试1 # ![在这里插入图片描述][20190717100624663.png] ## 输入 ## 5 7 1 0 4 3 2 1 2 0 3 2 4 1 4 2 ## 输出 ## 5 4 3 2 1 # 测试2 # ![在这里插入图片描述][20190717100729768.png] ## 输入 ## 5 8 0 3 1 0 4 3 2 1 2 0 3 2 4 1 4 2 # 输出 # 该图存在负环 [20190717100624663.png]: /images/20211205/5f3fb05964ae4d0bafa4810989ac6e86.png [20190717100729768.png]: /images/20211205/04cd00408bcc4c88bc9c63a37dafedcd.png
相关 拓扑排序 在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。 对于一个工程,我们首先将这 野性酷女/ 2022年06月10日 13:28/ 0 赞/ 197 阅读
相关 拓扑排序 C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N/ /假设不相连的边的Edge==INT_MAX/ void 淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 326 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 185 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 211 阅读
相关 拓扑排序 (1)有向无环图 无环的有向图,简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几 古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 246 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 295 阅读
相关 拓扑排序 拓扑排序 题目做的烦,题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from 谁借莪1个温暖的怀抱¢/ 2021年12月20日 16:11/ 0 赞/ 242 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 403 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 477 阅读
还没有评论,来说两句吧...