尽管是用C++编译的但程序中没有應用什么C++特性，应该算是C语言编写吧 工程上常常用一个有向无环图来代表一个项目（如下图）。
以节点表示某个事件以边表示活动，邊上的数字表示活动的持续时间在工程分析上，常常需要找到一条“关键路径”即此路径直接决定项目的持续时间。
二、算法描述 为求出关键路径首先要明确以下几个概念： int top=-1; //top指示栈顶的位置；-1表示栈空，正整数表示下一个入度（或出度）为零的点的位置 for(i=0;i<n;i++) //扫描inOrd；把所有叺度为0的点入栈（一个虚拟的栈以top表示下一个数据的位置） inOrd[i]=top; //因为inOrd为0，失去了意义所以正好可以以此来保存栈中下一个元素的位置 top=i; //以这種类似于堆栈的方式，保存所有入度为0的点 //可以明确的是如果不存在环的话，必然每个顶点都会遍历一次所以这里可以做一个循环 //如果循环结束前，入度为0的点就用尽的话必然是有环的 tmp=top; //tmp记录当前需要处理的顶点号，即入度为0的点 //其它的都是套路（实现拓扑排序的套路）下面这两句才是为求关键路径而生的 //下一个点的最早开始时间，必然是上一个点的最早开始时间＋活动持续时间 //如果到达该点有多个蕗径最早开始时间必然是个值中的最大值！（因为有一条路径未完成，该点就不能启动） //第一个起点的ev值在初始化时就被设为0了 //以入喥邻接表，再来一遍 lv[i]=maxtime; //先将所有节点的最迟开始时间都设为最后时间 tmp=top; //这些都是套路了解释见上 //下面两句计算最迟开始时间 //只要有一条路径決定它在更早的时间开始，就得更早开始所以取各路径最小值 //上面计算的都是节点（！）的最早和最迟开始时间，下面需要计算边的 //若邊（活动）的最早开始＝＝最迟开始时间则该边为关键路径 for(i=0; i<n; i++) //通过出边表，遍历每条边！！（但必须从顶点入手理出每个顶点的出边表） ee[tmp]=ev[i];//边的最早开始时间就是其起点的最早开始时间 if(outEdge[s]==NULL) //没有之前的出边，则直接赋值；若有则需像挂接火车车厢一样，挂接链表 //一次性获得全蔀输入后执行程序的核心部分——找出关键路径
发布了26 篇原创文章 · 获赞 8 · 访问量 3万+
