基于拓扑排序的排课程序 迈不过友情╰ 2022-05-23 13:35 123阅读 0赞 一、题目描述 某学院有n门课程,(i,j)表示课程i是课程j的先行课,及课程i必须在课程j的之前的学期开设。对任意给出的仙子那个课解s=\{(1,3),(2,4),(3,5),(4,6),(3,7),…\},至少需要安排多少个学期?给出每个学期的课程清单。 二、程序思路 分析题目能清楚地发现此题与拓扑排序有很大的关系,拓扑排序的层数就是学期数,每个学期的课程就是每一层的点。所以只需要在拓扑排序的程序上改改就好了。 三、具体实现 int linkedDgraph1::course(int **b)//传入的为保存结果的二维数组 { int number=0;//学期数 int n=verticeNumber;//顶点个数 int *indegree=new int[num1+1];//顶点的入度数组 for(int i=1;i<=num1;i++)//保存入度 indegree[i]=inDegree(i); stack<int> astack(10000);//声明栈 while(n!=0) { int j=0; for(int i=1;i<=num1;i++)//遍历将入度为零的点入栈 { if(indegree[i]==0) { b[number][j++]=i;//保存此点 //cout<<i<<" "; astack.push(i); //入栈 } } number++;//前一学期的课程已完 //cout<<number<<" "; while(!astack.empty()) { int t=astack.top(); n--; // cout<<verticeNumber<<" "; indegree[t]=-1; astack.pop(); for(int i=1;i<=num1;i++)//更新各顶点的入度 if(existsEdge(t,i)) indegree[i]--; } } return number; } 四、结果展示 ![图结构][70] ![输出结果][70 1] 五、说明 本程序所用图的结构为邻接链表。 [70]: /images/20220523/bbc62eb1e8da4efa90a56b210c224b69.png [70 1]: /images/20220523/4ef5fc13228048a4975b01f0ec6ff0e7.png
相关 拓扑排序 在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。 对于一个工程,我们首先将这 野性酷女/ 2022年06月10日 13:28/ 0 赞/ 202 阅读
相关 拓扑排序 C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N/ /假设不相连的边的Edge==INT_MAX/ void 淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 335 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 190 阅读
相关 【算法】基于AOV网的拓扑排序 写在前面:这篇文章在一周前就应该发的,后来因为腾讯面试拖到现在,虽然现在下动车也有一两个小时了,但是感觉自己好像还在路上颠簸。昨天去腾讯深圳总部面试,深圳总部啊!马爸爸在的 今天药忘吃喽~/ 2022年06月08日 07:22/ 0 赞/ 280 阅读
相关 基于拓扑排序的排课程序 一、题目描述 某学院有n门课程,(i,j)表示课程i是课程j的先行课,及课程i必须在课程j的之前的学期开设。对任意给出的仙子那个课解s=\{(1,3),(2,4),(3,5) 迈不过友情╰/ 2022年05月23日 13:35/ 0 赞/ 124 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 216 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 302 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 408 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 484 阅读
还没有评论,来说两句吧...