devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构之有向无环图——拓扑排序、AOV、AOE、关键路径_有向无环图所有路径 tcl

作者：知新_RL | 2024-03-17 21:55:26

赞

踩

有向无环图所有路径 tcl

一、介绍

1.有向无环图（DAG）

2.拓扑排序

1.偏序

2.全序

3.拓扑有序

4.拓扑排序

3.AOV(Activity On Vertex 顶点表示活动的网)

概念

举例

应用

4.AOE(Activity On Edge 边表示活动的网)

概念

举例

性质

5.关键路径

概念

举例

二、实现拓扑排序

算法思想

 算法实现

1.DAG的创建

2.拓扑排序

3.全部代码

代码执行结果

三、实现求关键路径

算法思想

算法实现

有向图类：

得到拓扑排序的逆排序getcontrarytopostack()：

求关键路径criticalpath():

全部代码：

代码执行结果

四、总结

一、介绍

1.有向无环图（DAG）

有向无环图(DAG:Directed Acycline Graph)指的是是图中无环的有向图

 我们要确定一个有向图是否为DAG，我们可以利用之前所学到的DFS深度优先搜索，查看是否存在一条路径可以从起点出发并再次回到起点

 如此图，我们选择顶点0进行DFS，那么按照深度优先遍历的规则，遍历顺序应该是0-1-2-4-3

在遍历每个顶点的时候，我们加入判断其是否产生了回路即可，因此当遍历到顶点4的时候，算法就会检测到回路的存在，因此该图不是一个DAG

2.拓扑排序

设我们现在有这么一个集合L={1,2,3,4},这个集合存在一个关系R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<1,3>,<3,1>,<1,4>,<4,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}，以及关系R1={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}

1.偏序

自反性：任取一个集合L中的元素x,<x,x>都存在于R中，那么关系R是自反的

example:不管我们选择哪个元素,从1到4,我们都能找到<1,1>到<4,4>存在于R中，因此R是自反的

对称性:任取集合L中的两个元素x和y,如果<x,y>在R中，那么<y,x>也在R中，那么关系R是对称的

example:我们选择1和3,<1,3>存在于R中,<3,1>也存在于R中，选择2和4,<2,4>存在于R中，<4,2>也存在于R中，那么关系R是对称的

反对称性：任取集合L中的两个元素x和y,如果<x,y>在R中，那么<y,x>就不在R中，那么关系R是反对称的

example:我们选择1和3，<1,3>在R1中,<3,1>不在R1中，选择2和4，<2,4>在R1中,<4,2>不在R1中，那么关系R1是反对称的

传递性：任取集合L中的三个元素x、y、z，如果<x,y>和<y,z>都存在于R中那么<x,z>也存在于R中，那么关系R是传递的

exm:我们选择1、3、4,<1,3>和<3,4>都存在于R中，且<1,4>也存在于R中，因此关系R是传递的

结论：如果R是自反的，反对称的，和传递的，则称R是A上的偏序关系

2.全序

如果关系R是集合X上的偏序，那么如果对于每个L中的x,y,R中必定有xRy或者yRx就可以称R是X上的全序关系(xRy 指的是元素x和元素y在R中的关系且是有序的)

偏序和全序的不同：

偏序指的是集合中只有部分成员之间可比较，全序指的是集合中的全体成员均可比较，因此全序时特殊的偏序

3.拓扑有序

如下图其实就存在偏序关系，因为顶点1和顶点3是没有先后关系的，因此当选取顶点1和顶点3的时候，你会发现无法满足偏序定义中的自反性、反对称性、传递性。

 但如如果我们加入顶点1和顶点3的先后关系后，这张图就变成了全序的了，如下图所示，此时整张图中的任取两个元素都将会满足偏序的关系，又因为全部元素任取两个都可以满足偏序关系，因此是全序的，此时我们就可以称下图为拓扑有序的。

4.拓扑排序

由偏序的定义得到的拓扑有序的操作称作拓扑排序，需要注意的是，拓扑排序针对的是DAG实现的，如果有向图中存在回路的话那么拓扑排序是不可实现的

拓扑排序算法流程：

1）在有向图中选择一个没有前驱的顶点并且将其输出

2）从图中将该顶点以及所有以这个顶点为尾的弧删除

3）重复1，2步直到所有的顶点都被输出

举例说明

 观察下图，存在0-1-2-0，0-3-2-0这两条回路，那么这个有向图无法进行拓扑排序

3.AOV(Activity On Vertex 顶点表示活动的网)

概念

i.AOV一定是DAG，即有向无环图

ii.如果用有向图的顶点表示活动，用弧表示活动之间的优先关系，那么我们就称该有向图为AOV

iii.AOV的应用包括流程图等等

举例

 如上图是一个有向无环图，我们按照拓扑排序的规则

拓扑排序算法流程：

1）在有向图中选择一个没有前驱的顶点并且将其输出

2）从图中将该顶点以及所有以这个顶点为尾的弧删除

3）重复1，2步直到所有的顶点都被输出

 我们先在这个DAG中寻找一个没有前驱的顶点，查询可以得到C1和C2这两个顶点，因此我们需要选择一个顶点，我们先选择C1并输出，然后继续按照规则可以得到下面的动图演示

 最后得到的拓扑排序输出为C1 , C8 , C9 , C2 , C3 , C4, C5 , C6 , C7

当然了可能有人会有疑问，删除了C4之后为什么先删除C5而不去删除C7，这里我们需要考虑到的是，每次递归我们都要涉及一个先后顺序的问题，而一般来说是从小到大进行遍历的，因此当发现序号较小的C5并且符合拓扑排序的规则的时候我们优先选择删除C5并输出

因此拓扑排序是有多种可能的，具体的拓扑排序结果要视代码的执行情况而定

应用

依然如上面的图一样，此时各个顶点代表的是一门课程，弧表示的是先修的关系，那么按照我们的拓扑排序我们可以得到对应的修学课程的顺序

4.AOE(Activity On Edge 边表示活动的网)

概念

i.AOV一定是DAG，即有向无环图

ii.如果用有向图的顶点表示事件，用弧表示活动，那么我们就称该有向图为AOV

iii.没有入弧的顶点称作源点，如下图中的顶点0

iv.没有出弧的顶点称作汇点，如下图中的顶点4

v.AOV的应用包括工程的完成时间等等

举例

 如上图所示顶点表示的就是相应的事件，弧表示的就是活动，弧上的权值表示的就是持续时间

性质

1.只有在进入某个顶点的全部活动都结束了，该顶点所代表的事件才会发生

example：如上图所示，只有当<1,2>和<3,2>都执行完毕了之后顶点2所代表的事件才会发生

2.只有在某个顶点所代表的事件结束之后，从该顶点出发的各活动才会开始

example：如上图所示，只有当顶点2所代表的事件执行完毕了，从顶点2出发的<2,4>活动才会开始

5.关键路径

概念

示例图

1.关键路径与关键活动

在AOE中，当所有活动完成才意味着一个工程的完成，因此完成整个工程所必须花费的时间，应该是从源点到汇点的最大路径长度，能具有最大路径长度的路径称为关键路径，而关键路径上的活动称为关键活动

2.事件的最早发生时间:ve[k](ve代表着事件对应的vertex和earliest)

计算方式：从源点开始

当全部进入事件的活动都结束之后这个事件才可以进行，设有两个活动<i,k>和<j,k>进入事件k,因此事件k的最早发生时间为ve[k]=max(ve[j]+length<j,k> , ve[i]+length<i,k>)

exmaple:我们要求事件4的最早发生时间,ve[4]=max( ve[1]+length<1,4> ,ve[2]+length<2,4> )

因为一个工程是从源点开始的，因此事件0的最早发生时间ve[0]=0,事件1只有一个活动进入也就是<0,1>,因此ve[1]=ve[0]+leng<0,1>=2,同理可求ve[2]=ve[0]+length<0,2>=1,因此ve[4]=max(6,6)=6,因此事件4的最早开始时间就是6,最终我们还可以求得事件5也就是汇点的最早发生时间=9

3.事件的最迟发生时间:vl[k](vl代表着事件对应的vertex和latest)

计算方式：从汇点开始

设有两个活动<k,i>,<k,j>从事件k出发，分别到达事件i和事件j，那么vl[k]=min(vl[i]-length<k,i>,vl[j]-length<k,j>)

example:我们要求事件1的最晚发生时间，vl[1]=min(vl[3]-length<1,3>,vl[4]-length<1,4>)

当求出汇点事件的最早发生时间之后，也就求出了汇点的最迟发生时间，即ve[汇点]=vl[汇点]=9，同时ve[源点]=vl[源点]=0,那么我们根据最迟发生时间的计算方式我们可以得到vl[3]=vl[5]-length<3,5>=5,vl[4]=vl[5]-length<4,5>=7,因此vl[1]=min(vl[3]-length<1,3>,vl[4]-length<1,4>)=min(2,3)=2

4.活动的最早发生时间:ee[i](ee:event earliest)

由于代表事件的顶点的出弧代表活动，当该事件未发生的时候活动自然也没法发生，因此活动的最早发生时间就是代表活动的弧尾顶点所代表事件的最早发生时间,我们将全部弧按照一定的顺序排序并且赋予一个下标(a0-a6)，由此我们可以得到:

ee[0]=ve[0]=0        ee[1]=ve[0]=0       ee[2]=ve[1]=2        ee[3]=ve[1]=2         ee[4]:=ve[2]=1       ee[5]=ve[3]=5        ee[6]=ve[4]=6

5.活动的最迟发生时间:el[k](el:event latest)

同理我们可以得到:

el[0]=vl[1]-a0=0        el[1]=vl[2]-a1=1        el[2]=vl[3]-a2=2        el[3]=vl[4]-a3=3        el[4]=vl[4]-a4=2        el[5]=vl[5]=9

举例

 如上图所示是一个AOE,根据上面对相关概念的解释，我们可以知道这个AOE的关键路径是0-1-4-5,关键顶点是0、1、4、5,事件0的最早发生时间为0，事件1的最早发生时间为ve[0]+length<0,2>=2,事件4的最迟发生时间为max(vl[1]+length<1,4> , vl[2]+length<2,4>)=6,活动最早发生时间和活动最晚发生时间以此类推就好

二、实现拓扑排序

算法思想

拓扑排序算法流程：

1）在有向图中选择一个没有前驱的顶点并且将其输出

2）从图中将该顶点以及所有以这个顶点为尾的弧删除

3）重复1，2步直到所有的顶点都被输出

 算法实现

1.DAG的创建

我们在这里选择使用邻接矩阵来储存DAG，adjmatrix[i][j]=-1表示顶点i无法找到一条弧直接到达顶点j,adjmatrix[i][i]表示的是自身到自身的弧的距离，我们可以知道，一个DAG中是无法找到一个自身到自身的弧的，因此我们也赋值为-1

有向图类：

  1. class indigraph
  2. {
  3.     public:
  4.     int maxvertexindex=0;//最大顶点序号
  5.     int flag[maxsize];//用来标志一个顶点是否被访问
  6.     int adjmatrix[maxsize][maxsize];//邻接矩阵用来存储有向图
  7.     void createindigraph();//创建有向图
  8.     void initflag();
  9.     void initadjmatrix();
  10.     void topo();//拓扑排序
  11.     void printadjmatrix();//打印邻接矩阵
  12. };

创建有向图：

  1. void indigraph::createindigraph()
  2. {
  3.     int bowtail;//弧尾顶点
  4.     int weight;//权重
  5.     int symbol=0;//标志位
  6.     for(int i=0;symbol==0;i++)
  7.     {
  8.         while (true)
  9.         {
  10.             cout<<"请输入顶点"<<i<<"的出弧弧尾:"<<endl;
  11.             cin>>bowtail;
  12.             if (bowtail>maxvertexindex)
  13.             {
  14.                 maxvertexindex=bowtail;
  15.             }
  16.             if (bowtail==-1)
  17.             {
  18.                 break;
  19.             }
  20.             if (bowtail==-2)
  21.             {
  22.                 symbol=1;
  23.                 break;
  24.             }
  25.             cout<<"请输入弧<"<<i<<","<<bowtail<<">的权值:"<<endl;
  26.             cin>>weight;
  27.             adjmatrix[i][bowtail]=weight;
  28.         }
  29.     }
  30.     cout<<"邻接矩阵构建完毕"<<endl;
  31. }

打印有向图邻接矩阵：

  1. void indigraph::printadjmatrix()
  2. {
  3.     cout<<"============adjmatrix================"<<endl;
  4.     for (int i = 0; i <maxvertexindex+1; i++)
  5.     {
  6.         for (int j = 0; j < maxvertexindex+1; j++)
  7.         {
  8.             cout<<adjmatrix[i][j]<<"  ";
  9.         }
  10.         cout<<endl;
  11.     }
  12.     cout<<"====================================="<<endl;
  13. }

2.拓扑排序

根据算法思想中的拓扑排序算法流程，我们需要先找到没有前驱的顶点，在邻接矩阵adjmatrix[][]中，adjmatrix[i][j]表示的是从顶点i到达顶点j的弧，i为弧尾，j为弧头，其中的数值为弧的权值，因此如果我们要确定一个顶点k是否有前驱顶点，我们只需要遍历adjmatrix[][k],如果发现存在值不为无穷大，则说明存在一个顶点到达顶点k，那么顶点k就有前驱顶点，反之如果遍历完毕之后发现所有值都为无穷大那么就说明这个顶点没有前驱顶点

  1. void indigraph::topo()
  2. {
  3.     int i,j;
  4.     queue<int> q;//创建一个队列用来存放每次找到的无前驱顶点的顶点
  5.     queue<int> topoqueue;//创建一个队列用来存储拓扑排序的结果
  6.     while(topoqueue.size()!=5)
  7.     {
  8.         for (i = 0; i < maxvertexindex+1; i++)//两层循环用来对整个邻接矩阵进行遍历
  9.         {
  10.             for (j = 0; j < maxvertexindex+1; j++)
  11.             {
  12.                 if (adjmatrix[j][i]!=-1)//一旦发现某一列存在非-1的的数值说明该列对应的顶点不是无前驱顶点
  13.                 {
  14.                     break;
  15.                 }
  16.             }  
  17.             if (j==maxvertexindex+1&&flag[i]!=1)//当遍历完整列并且发现该列对应的顶点未被访问过
  18.             {
  19.                 q.push(i);//临时队列添加无前驱顶点
  20.                 topoqueue.push(i);//结果队列添加无前驱顶点
  21.                 flag[i]=1;//标记这个顶点被访问过
  22.             } 
  23.         }
  24.         while (q.empty()!=true)//当临时队列不为空说明还没访问完毕
  25.         {
  26.             int v=q.front();//存储临时队列的头元素
  27.             q.pop();//弹出元素
  28.             for (int i = 0; i < maxvertexindex+1; i++)//并将对应顶点所参与的弧删除
  29.             {
  30.                 adjmatrix[v][i]=-1;//标记为-1就意味着删除
  31.             }
  32.         }
  33.  
  34.     }
  35.     cout<<"拓扑排序为:"<<endl;//输出拓扑排序结果
  36.     while (topoqueue.size()!=0)
  37.     {
  38.         cout<<topoqueue.front()<<"  ";
  39.         topoqueue.pop();
  40.     }
  41. }

3.全部代码

  1.  #include<stdio.h>
  2.  #include<iostream>
  3.  #include<queue>
  4.  #define maxsize 100
  5.  #define infi 999
  6.  using namespace std;
  7.  
  8. class indigraph
  9. {
  10.     public:
  11.     int maxvertexindex=0;//最大顶点序号
  12.     int flag[maxsize];//用来标志一个顶点是否被访问
  13.     int adjmatrix[maxsize][maxsize];//邻接矩阵用来存储有向图
  14.     void createindigraph();//创建有向图
  15.     void initadjmatrix();
  16.     void initflag();
  17.     void topo();//拓扑排序
  18.     void printadjmatrix();//打印邻接矩阵
  19. };
  20.  
  21. void indigraph::createindigraph()
  22. {
  23.     int bowtail;//弧尾顶点
  24.     int weight;//权重
  25.     int symbol=0;//标志位
  26.     for(int i=0,k=0;symbol==0;i++)
  27.     {
  28.         while (true)
  29.         {
  30.             cout<<"请输入顶点"<<i<<"的出弧弧尾:"<<endl;
  31.             cin>>bowtail;
  32.             if (bowtail>maxvertexindex)
  33.             {
  34.                 maxvertexindex=bowtail;
  35.             }
  36.             if (bowtail==-1)
  37.             {
  38.                 break;
  39.             }
  40.             if (bowtail==-2)
  41.             {
  42.                 symbol=1;
  43.                 break;
  44.             }
  45.             if (i>maxvertexindex)
  46.             {
  47.                 maxvertexindex=i;
  48.             }
  49.             cout<<"请输入弧<"<<i<<","<<bowtail<<">的权值:"<<endl;
  50.             cin>>weight;
  51.             adjmatrix[i][bowtail]=weight;
  52.         }
  53.     }
  54.     cout<<"邻接矩阵构建完毕"<<endl;
  55. }
  56.  
  57. void indigraph::initadjmatrix()
  58. {
  59.     for (int i = 0; i < maxsize; i++)
  60.     {
  61.         for (int j = 0; j < maxsize; j++)
  62.         {
  63.             adjmatrix[i][j]=-1;
  64.         }
  65.     }
  66. }
  67.  
  68. void indigraph::initflag()
  69. {
  70.     for (int i = 0; i < maxvertexindex; i++)
  71.     {
  72.         flag[i]=0;
  73.     }
  74.     
  75. }
  76.  
  77. void indigraph::printadjmatrix()
  78. {
  79.     cout<<"======adjmatrix======"<<endl;
  80.     for (int i = 0; i <maxvertexindex+1; i++)
  81.     {
  82.         for (int j = 0; j < maxvertexindex+1; j++)
  83.         {
  84.             cout<<adjmatrix[i][j]<<"  ";
  85.         }
  86.         cout<<endl;
  87.     }
  88.     cout<<"====================="<<endl;
  89. }
  90.  
  91. void indigraph::topo()
  92. {
  93.     int i,j;
  94.     queue<int> q;//创建一个队列用来存放每次找到的无前驱顶点的顶点
  95.     queue<int> topoqueue;//创建一个队列用来存储拓扑排序的结果
  96.     while(topoqueue.size()!=maxvertexindex+1)
  97.     {
  98.         for (i = 0; i < maxvertexindex+1; i++)//两层循环用来对整个邻接矩阵进行遍历
  99.         {
  100.             for (j = 0; j < maxvertexindex+1; j++)
  101.             {
  102.                 if (adjmatrix[j][i]!=-1)//一旦发现某一列存在非-1的的数值说明该列对应的顶点不是无前驱顶点
  103.                 {
  104.                     break;
  105.                 }
  106.             }  
  107.             if (j==maxvertexindex+1&&flag[i]!=1)//当遍历完整列并且发现该列对应的顶点未被访问过
  108.             {
  109.                 q.push(i);//临时队列添加无前驱顶点
  110.                 topoqueue.push(i);//结果队列添加无前驱顶点
  111.                 flag[i]=1;//标记这个顶点被访问过
  112.             } 
  113.         }
  114.         while (q.empty()!=true)//当临时队列不为空说明还没访问完毕
  115.         {
  116.             int v=q.front();//存储临时队列的头元素
  117.             q.pop();//弹出元素
  118.             for (int i = 0; i < maxvertexindex+1; i++)//并将对应顶点所参与的弧删除
  119.             {
  120.                 adjmatrix[v][i]=-1;//标记为-1就意味着删除
  121.             }
  122.         }
  123.  
  124.     }
  125.     cout<<"拓扑排序为:"<<endl;//输出拓扑排序结果
  126.     while (topoqueue.size()!=0)
  127.     {
  128.         cout<<topoqueue.front()<<"  ";
  129.         topoqueue.pop();
  130.     }
  131. }
  132.  
  133.  int main()
  134.  {
  135.     indigraph ig;
  136.     ig.initadjmatrix();
  137.     ig.initflag();
  138.     ig.createindigraph();
  139.     ig.printadjmatrix();
  140.     ig.topo();
  141.     return 0;
  142.  }

代码执行结果

 如上图是一个DAG，我们将其导入到该算法之中我们可以得到下图的结果：

三、实现求关键路径

 

如上图所示是一个工程的进度计划，用AOE表示，现在我们要求出这个工程的最短工期和关键路径，从而知道应该缩短什么活动的事件从而缩短工期

算法思想

1.求出所有事件的最早发生时间

2.由所有事件的最早发生时间求出所有活动的最早发生时间

3.由汇点事件的最早发生时间得到汇点事件的最迟发生时间

4.由汇点事件的最迟发生时间求出所有事件的最迟发生时间

5.由所有事件的最迟发生时间求出所有活动的最迟发生时间

6.对比活动的最早发生时间和最迟发生时间，相同的即为关键活动，关键活动经过的事件就是关键顶点

7.由关键活动或关键事件就可以得到关键路径

算法实现

有向图类：

tips：为了方便测试，我将AOE图直接存入了有向图类中，如果想要测试其他图的话请按照下面代码中注释的提示来操作

我们可以知道，我们已经实现了拓扑排序并且能将结果储存在一个队列topoqueue中，对于我们求取事件的最晚发生时间时，我们要按照逆拓扑排序来对事件进行操作，那么要怎么得到一个逆拓扑排序的数据结构呢，我们可以使用栈，当我们把队列的元素依次弹出并放入栈中，此时我们就得到了逆拓扑排序，只要我们不断取出栈顶的数，取出的数字顺序就是逆拓扑排序的顺序，因此我们就创建了下图的三种数据结构

  1.     queue<int> topoqueue;//创建一个队列用来存储拓扑排序的结果
  2.     queue<int> transferqueue;//创建一个临时队列用来间接得到存放拓扑排序的逆排序栈
  3.     stack<int> contrarytopostack;//创建一个栈用来存放拓扑排序的逆排序栈

 并且我们为了比较最早时间和最迟时间，我们需要创建多个数组分别是ve[],vl[],ee[],el[]用来存储这些时间结果，并且我们在进行对比之后我们还需要一个队列criticalevent[]用来存储关键事件,一个数组criticalactivity[]用来储存关键活动，下图就是有向图类的全部成员变量和成员函数

  1. class indigraph
  2. {
  3.     public:
  4.     queue<int> topoqueue;//创建一个队列用来存储拓扑排序的结果
  5.     queue<int> transferqueue;//创建一个临时队列用来间接得到存放拓扑排序的逆排序栈
  6.     stack<int> contrarytopostack;//创建一个栈用来存放拓扑排序的逆排序栈
  7.     int ve[maxsize];//事件的最早发生时间
  8.     int vl[maxsize];//事件的最迟发生时间
  9.     int ee[maxsize];//活动的最早发生时间
  10.     int el[maxsize];//活动的最迟发生时间
  11.     queue<int> criticalevent;//关键事件
  12.     int criticalactivity[maxsize];//关键活动
  13.     //int arcnum;//如果是自己输入图就取消这一行的注释并注释下一行
  14.     int arcnum=14;
  15.     //int maxvertexindex=0;//如果是自己输入图就取消这一行的注释并注释下一行
  16.     int maxvertexindex=9;//最大顶点序号
  17.     int flag[maxsize];//用来标志一个顶点是否被访问
  18.     //int adjmatrix[maxsize][maxsize];//如果是自己输入图就取消这一行的注释并注释下一行
  19.     int adjmatrix[maxsize][maxsize]=//邻接矩阵用来存储有向图
  20.     {   {-1,5,6,-1,-1,-1,-1,-1,-1,-1},//0
  21.         {-1,-1,-1,3,-1,-1,-1,-1,-1,-1},//1
  22.         {-1,-1,-1,12,3,-1,-1,-1,-1,-1},//2
  23.         {-1,-1,-1,-1,3,3,5,-1,-1,-1},//3
  24.         {-1,-1,-1,-1,-1,-1,1,4,-1,-1},//4
  25.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,4},//5
  26.         {-1,-1,-1,-1,-1,-1,-1,-1,5,-1},//6
  27.         {-1,-1,-1,-1,-1,-1,-1,-1,2,-1},//7
  28.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,2},//8
  29.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}//9
  30.     };
  31.     void createindigraph();//创建有向图
  32.     void initadjmatrix();//初始化邻接矩阵
  33.     void initflag();//初始化访问数组
  34.     void getcontrarytopostack();//得到拓扑排序的逆排序
  35.     void topo();//拓扑排序
  36.     void criticalpath();//求关键路径
  37.     void printadjmatrix();//打印AOE图的邻接矩阵
  38. };

得到拓扑排序的逆排序getcontrarytopostack()：

  1. void indigraph::getcontrarytopostack()
  2. {
  3.     while (transferqueue.empty()!=true)
  4.     {
  5.         contrarytopostack.push(transferqueue.front());
  6.         transferqueue.pop();
  7.     }   
  8. }

求关键路径criticalpath():

  1. void indigraph::criticalpath()
  2. {
  3.     //求出所有事件的最早发生时间
  4.     int source=topoqueue.front();//求源点
  5.     cout<<source<<endl;
  6.     ve[source]=0;//源点的最早发生时间为0
  7.     cout<<"ve["<<source<<"]:"<<0<<"   ";
  8.     topoqueue.pop();//源点弹出
  9.     while (topoqueue.empty()!=true)
  10.     {
  11.         int tempvertex=topoqueue.front();
  12.         //cout<<"当前操作的顶点为"<<tempvertex<<endl;
  13.         int tempmax=0;
  14.         for (int i = 0; i < maxvertexindex+1; i++)
  15.         {
  16.             if (adjmatrix[i][tempvertex]!=-1&&ve[i]+adjmatrix[i][tempvertex]>tempmax)
  17.             {
  18.                 //cout<<"查询到弧:<"<<i<<","<<tempvertex<<">"<<endl;
  19.                 //cout<<"该弧对应的最早发生时间为:"<<ve[i]+adjmatrix[i][tempvertex]<<endl;
  20.                 tempmax=ve[i]+adjmatrix[i][tempvertex];
  21.                 //cout<<"tempmax="<<tempmax<<endl;    
  22.             }  
  23.         }
  24.         ve[tempvertex]=tempmax;
  25.         cout<<"ve["<<tempvertex<<"]:"<<tempmax<<"   ";
  26.         topoqueue.pop();
  27.     }
  28.  
  29.     //求出所有活动的最早发生时间
  30.     int k=0;
  31.     for (int i = 0; i < maxvertexindex+1; i++)
  32.     {
  33.         for (int j = 0; j < maxvertexindex+1; j++)
  34.         {
  35.             if (adjmatrix[i][j]!=-1)
  36.             {
  37.                 ee[k]=ve[i];
  38.                 k+=1;
  39.             }
  40.         }
  41.     }
  42.  
  43.     cout<<endl;
  44.     //求出所有事件的最迟发生时间
  45.     getcontrarytopostack();//得到存放拓扑排序的栈，并且只能从尾部开始取数，因此取数的顺序就成为了逆拓扑排序
  46.     vl[contrarytopostack.top()]=ve[contrarytopostack.top()];//汇点事件的最迟发生时间=汇点事件的最早发生时间
  47.     cout<<"vl["<<contrarytopostack.top()<<"]:"<<ve[contrarytopostack.top()]<<"   ";
  48.     contrarytopostack.pop();
  49.     while (contrarytopostack.empty()!=true)
  50.     {
  51.         int tempvertex1=contrarytopostack.top();
  52.         //cout<<"当前操作的顶点为"<<tempvertex1<<endl;
  53.         int tempmin=infi;
  54.         for (int i = 0; i < maxvertexindex+1; i++)
  55.         {
  56.             if (adjmatrix[tempvertex1][i]!=-1&&vl[i]-adjmatrix[tempvertex1][i]<tempmin)
  57.             {
  58.                 //cout<<"查询到弧:<"<<tempvertex1<<","<<i<<">"<<endl;
  59.                 //cout<<"该弧对应的最迟发生时间为:"<<vl[i]-adjmatrix[tempvertex1][i]<<endl;
  60.                 tempmin=vl[i]-adjmatrix[tempvertex1][i];
  61.                 //cout<<"tempmin="<<tempmin<<endl;    
  62.             }  
  63.         }
  64.         vl[tempvertex1]=tempmin;
  65.         cout<<"vl["<<tempvertex1<<"]:"<<tempmin<<"   ";
  66.         contrarytopostack.pop();
  67.     }
  68.  
  69.  
  70.     //求出所有活动的最迟发生时间
  71.     k=0;
  72.     for (int i = 0; i < maxvertexindex+1; i++)
  73.     {
  74.         for (int j = 0; j < maxvertexindex+1; j++)
  75.         {
  76.             if (adjmatrix[i][j]!=-1)
  77.             {
  78.                 el[k]=vl[i];
  79.                 k+=1;
  80.             }
  81.         }
  82.     }
  83.     cout<<endl;
  84.     //求出最早发生时间和最迟发生时间相同的事件即关键事件
  85.     for (int i = 0; i < maxvertexindex+1; i++)
  86.     {
  87.         if (ve[i]==vl[i])
  88.         {
  89.             cout<<"事件"<<i<<"的最早发生时间和最迟发生时间相同"<<endl;
  90.             criticalevent.push(i);
  91.         } 
  92.     }
  93.     cout<<"criticalevent.size()="<<criticalevent.size()<<endl;
  94.     //求出最早发生时间和最迟发生时间相同的活动即关键活动
  95.     int p=0;
  96.     for (int i = 0; i < 14; i++)
  97.     {
  98.         if (ee[i]==el[i])
  99.         {
  100.             cout<<"活动a"<<i+1<<"的最早发生时间和最迟发生时间相同"<<endl;
  101.             criticalactivity[p]=i+1;
  102.             p+=1;
  103.         } 
  104.     }
  105.     
  106.     //由关键事件或关键活动得到关键路径
  107.     //由关键事件得到关键路径
  108.     int temp;
  109.     int length=criticalevent.size()-1;
  110.     for (int i = 0; i <length; i++)
  111.     {
  112.         temp=criticalevent.front();
  113.         criticalevent.pop();
  114.         cout<<temp<<"---"<<adjmatrix[temp][criticalevent.front()]<<"---"<<criticalevent.front()<<endl;
  115.     }
  116.     
  117. }

全部代码：

  1.  #include<stdio.h>
  2.  #include<iostream>
  3.  #include<queue>
  4.  #include<stack>
  5.  #define maxsize 100
  6.  #define infi 999
  7.  using namespace std;
  8.  
  9. class indigraph
  10. {
  11.     public:
  12.     queue<int> topoqueue;//创建一个队列用来存储拓扑排序的结果
  13.     queue<int> transferqueue;//创建一个临时队列用来间接得到存放拓扑排序的逆排序栈
  14.     stack<int> contrarytopostack;//创建一个栈用来存放拓扑排序的逆排序栈
  15.     int ve[maxsize];//事件的最早发生时间
  16.     int vl[maxsize];//事件的最迟发生时间
  17.     int ee[maxsize];//活动的最早发生时间
  18.     int el[maxsize];//活动的最迟发生时间
  19.     queue<int> criticalevent;//关键事件
  20.     int criticalactivity[maxsize];//关键活动
  21.     //int arcnum;//如果是自己输入图就取消这一行的注释并注释下一行
  22.     int arcnum=14;
  23.     //int maxvertexindex=0;//如果是自己输入图就取消这一行的注释并注释下一行
  24.     int maxvertexindex=9;//最大顶点序号
  25.     int flag[maxsize];//用来标志一个顶点是否被访问
  26.     //int adjmatrix[maxsize][maxsize];//如果是自己输入图就取消这一行的注释并注释下一行
  27.     int adjmatrix[maxsize][maxsize]=//邻接矩阵用来存储有向图
  28.     {   {-1,5,6,-1,-1,-1,-1,-1,-1,-1},//0
  29.         {-1,-1,-1,3,-1,-1,-1,-1,-1,-1},//1
  30.         {-1,-1,-1,12,3,-1,-1,-1,-1,-1},//2
  31.         {-1,-1,-1,-1,3,3,5,-1,-1,-1},//3
  32.         {-1,-1,-1,-1,-1,-1,1,4,-1,-1},//4
  33.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,4},//5
  34.         {-1,-1,-1,-1,-1,-1,-1,-1,5,-1},//6
  35.         {-1,-1,-1,-1,-1,-1,-1,-1,2,-1},//7
  36.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,2},//8
  37.         {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}//9
  38.     };
  39.     void createindigraph();//创建有向图
  40.     void initadjmatrix();//初始化邻接矩阵
  41.     void initflag();//初始化访问数组
  42.     void getcontrarytopostack();//得到拓扑排序的逆排序
  43.     void topo();//拓扑排序
  44.     void criticalpath();//求关键路径
  45.     void printadjmatrix();//打印AOE图的邻接矩阵
  46. };
  47.  
  48. void indigraph::createindigraph()
  49. {
  50.     initadjmatrix();
  51.     initflag();
  52.     int bowtail;//弧尾顶点
  53.     int time;//权重
  54.     int symbol=0;//标志位
  55.     for(int i=0,k=0;symbol==0;i++)
  56.     {
  57.         while (true)
  58.         {
  59.             cout<<"请输入事件"<<i<<"的出弧弧尾:"<<endl;
  60.             cin>>bowtail;
  61.             if (bowtail>maxvertexindex)
  62.             {
  63.                 maxvertexindex=bowtail;
  64.             }
  65.             if (bowtail==-1)
  66.             {
  67.                 break;
  68.             }
  69.             if (bowtail==-2)
  70.             {
  71.                 symbol=1;
  72.                 break;
  73.             }
  74.             if (i>maxvertexindex)
  75.             {
  76.                 maxvertexindex=i;
  77.             }
  78.             arcnum+=1;
  79.             cout<<"请输入活动<"<<i<<","<<bowtail<<">的时间:"<<endl;
  80.             cin>>time;
  81.             adjmatrix[i][bowtail]=time;
  82.         }
  83.     }
  84.     cout<<"邻接矩阵构建完毕"<<endl;
  85. }
  86.  
  87. void indigraph::initadjmatrix()
  88. {
  89.     for (int i = 0; i < maxsize; i++)
  90.     {
  91.         for (int j = 0; j < maxsize; j++)
  92.         {
  93.             adjmatrix[i][j]=-1;
  94.         }
  95.     }
  96. }
  97.  
  98. void indigraph::initflag()
  99. {
  100.     for (int i = 0; i < maxvertexindex; i++)
  101.     {
  102.         flag[i]=0;
  103.     }
  104.     
  105. }
  106.  
  107. void indigraph::printadjmatrix()
  108. {
  109.     cout<<"=============adjmatrix============="<<endl;
  110.     for (int i = 0; i <maxvertexindex+1; i++)
  111.     {
  112.         for (int j = 0; j < maxvertexindex+1; j++)
  113.         {
  114.             cout<<adjmatrix[i][j]<<"  ";
  115.         }
  116.         cout<<endl;
  117.     }
  118.     cout<<"==================================="<<endl;
  119. }
  120.  
  121. void indigraph::topo()
  122. {
  123.     int i,j;
  124.     queue<int> q;//创建一个队列用来存放每次找到的无前驱顶点的顶点
  125.     int tempadjmatrix[maxsize][maxsize];
  126.     for (int i = 0; i < maxvertexindex+1; i++)
  127.     {
  128.         for (int j = 0; j < maxvertexindex+1; j++)
  129.         {
  130.             tempadjmatrix[i][j]=adjmatrix[i][j];
  131.         }
  132.         
  133.     }
  134.     
  135.     while(topoqueue.size()!=maxvertexindex+1)
  136.     {
  137.         for (i = 0; i < maxvertexindex+1; i++)//两层循环用来对整个邻接矩阵进行遍历
  138.         {
  139.             for (j = 0; j < maxvertexindex+1; j++)
  140.             {
  141.                 if (tempadjmatrix[j][i]!=-1)//一旦发现某一列存在非-1的的数值说明该列对应的顶点不是无前驱顶点
  142.                 {
  143.                     break;
  144.                 }
  145.             }  
  146.             if (j==maxvertexindex+1&&flag[i]!=1)//当遍历完整列并且发现该列对应的顶点未被访问过
  147.             {
  148.                 q.push(i);//临时队列添加无前驱顶点
  149.                 topoqueue.push(i);//结果队列添加无前驱顶点
  150.                 flag[i]=1;//标记这个顶点被访问过
  151.             } 
  152.         }
  153.         while (q.empty()!=true)//当临时队列不为空说明还没访问完毕
  154.         {
  155.             int v=q.front();//存储临时队列的头元素
  156.             q.pop();//弹出元素
  157.             for (int i = 0; i < maxvertexindex+1; i++)//并将对应顶点所参与的弧删除
  158.             {
  159.                 tempadjmatrix[v][i]=-1;//标记为-1就意味着删除
  160.             }
  161.         }
  162.  
  163.     }
  164.     cout<<"拓扑排序为:"<<endl;//输出拓扑排序结果
  165.     queue<int> tempqueue;
  166.     while (topoqueue.size()!=0)
  167.     {
  168.         cout<<topoqueue.front()<<"  ";
  169.         tempqueue.push(topoqueue.front());
  170.         transferqueue.push(topoqueue.front());
  171.         topoqueue.pop();
  172.     }
  173.     while (tempqueue.empty()!=true)
  174.     {
  175.         topoqueue.push(tempqueue.front());
  176.         tempqueue.pop();
  177.     }
  178.     
  179. }
  180.  
  181. void indigraph::getcontrarytopostack()
  182. {
  183.     while (transferqueue.empty()!=true)
  184.     {
  185.         contrarytopostack.push(transferqueue.front());
  186.         transferqueue.pop();
  187.     }   
  188. }
  189.  
  190. void indigraph::criticalpath()
  191. {
  192.     //求出所有事件的最早发生时间
  193.     int source=topoqueue.front();//求源点
  194.     cout<<source<<endl;
  195.     ve[source]=0;//源点的最早发生时间为0
  196.     cout<<"ve["<<source<<"]:"<<0<<"   ";
  197.     topoqueue.pop();//源点弹出
  198.     while (topoqueue.empty()!=true)
  199.     {
  200.         int tempvertex=topoqueue.front();
  201.         //cout<<"当前操作的顶点为"<<tempvertex<<endl;
  202.         int tempmax=0;
  203.         for (int i = 0; i < maxvertexindex+1; i++)
  204.         {
  205.             if (adjmatrix[i][tempvertex]!=-1&&ve[i]+adjmatrix[i][tempvertex]>tempmax)
  206.             {
  207.                 //cout<<"查询到弧:<"<<i<<","<<tempvertex<<">"<<endl;
  208.                 //cout<<"该弧对应的最早发生时间为:"<<ve[i]+adjmatrix[i][tempvertex]<<endl;
  209.                 tempmax=ve[i]+adjmatrix[i][tempvertex];
  210.                 //cout<<"tempmax="<<tempmax<<endl;    
  211.             }  
  212.         }
  213.         ve[tempvertex]=tempmax;
  214.         cout<<"ve["<<tempvertex<<"]:"<<tempmax<<"   ";
  215.         topoqueue.pop();
  216.     }
  217.  
  218.     //求出所有活动的最早发生时间
  219.     int k=0;
  220.     for (int i = 0; i < maxvertexindex+1; i++)
  221.     {
  222.         for (int j = 0; j < maxvertexindex+1; j++)
  223.         {
  224.             if (adjmatrix[i][j]!=-1)
  225.             {
  226.                 ee[k]=ve[i];
  227.                 k+=1;
  228.             }
  229.         }
  230.     }
  231.  
  232.     cout<<endl;
  233.     //求出所有事件的最迟发生时间
  234.     getcontrarytopostack();//得到存放拓扑排序的栈，并且只能从尾部开始取数，因此取数的顺序就成为了逆拓扑排序
  235.     vl[contrarytopostack.top()]=ve[contrarytopostack.top()];//汇点事件的最迟发生时间=汇点事件的最早发生时间
  236.     cout<<"vl["<<contrarytopostack.top()<<"]:"<<ve[contrarytopostack.top()]<<"   ";
  237.     contrarytopostack.pop();
  238.     while (contrarytopostack.empty()!=true)
  239.     {
  240.         int tempvertex1=contrarytopostack.top();
  241.         //cout<<"当前操作的顶点为"<<tempvertex1<<endl;
  242.         int tempmin=infi;
  243.         for (int i = 0; i < maxvertexindex+1; i++)
  244.         {
  245.             if (adjmatrix[tempvertex1][i]!=-1&&vl[i]-adjmatrix[tempvertex1][i]<tempmin)
  246.             {
  247.                 //cout<<"查询到弧:<"<<tempvertex1<<","<<i<<">"<<endl;
  248.                 //cout<<"该弧对应的最迟发生时间为:"<<vl[i]-adjmatrix[tempvertex1][i]<<endl;
  249.                 tempmin=vl[i]-adjmatrix[tempvertex1][i];
  250.                 //cout<<"tempmin="<<tempmin<<endl;    
  251.             }  
  252.         }
  253.         vl[tempvertex1]=tempmin;
  254.         cout<<"vl["<<tempvertex1<<"]:"<<tempmin<<"   ";
  255.         contrarytopostack.pop();
  256.     }
  257.  
  258.  
  259.     //求出所有活动的最迟发生时间
  260.     k=0;
  261.     for (int i = 0; i < maxvertexindex+1; i++)
  262.     {
  263.         for (int j = 0; j < maxvertexindex+1; j++)
  264.         {
  265.             if (adjmatrix[i][j]!=-1)
  266.             {
  267.                 el[k]=vl[i];
  268.                 k+=1;
  269.             }
  270.         }
  271.     }
  272.     cout<<endl;
  273.     //求出最早发生时间和最迟发生时间相同的事件即关键事件
  274.     for (int i = 0; i < maxvertexindex+1; i++)
  275.     {
  276.         if (ve[i]==vl[i])
  277.         {
  278.             cout<<"事件"<<i<<"的最早发生时间和最迟发生时间相同"<<endl;
  279.             criticalevent.push(i);
  280.         } 
  281.     }
  282.     cout<<"criticalevent.size()="<<criticalevent.size()<<endl;
  283.     //求出最早发生时间和最迟发生时间相同的活动即关键活动
  284.     int p=0;
  285.     for (int i = 0; i < 14; i++)
  286.     {
  287.         if (ee[i]==el[i])
  288.         {
  289.             cout<<"活动a"<<i+1<<"的最早发生时间和最迟发生时间相同"<<endl;
  290.             criticalactivity[p]=i+1;
  291.             p+=1;
  292.         } 
  293.     }
  294.     
  295.     //由关键事件或关键活动得到关键路径
  296.     //由关键事件得到关键路径
  297.     int temp;
  298.     int length=criticalevent.size()-1;
  299.     for (int i = 0; i <length; i++)
  300.     {
  301.         temp=criticalevent.front();
  302.         criticalevent.pop();
  303.         cout<<temp<<"---"<<adjmatrix[temp][criticalevent.front()]<<"---"<<criticalevent.front()<<endl;
  304.     }
  305.     
  306. }
  307.  
  308.  int main()
  309.  {
  310.     indigraph ig;
  311.     ig.initflag();
  312.     ig.printadjmatrix();
  313.     ig.topo();
  314.     ig.criticalpath();
  315.     return 0;
  316.  }

代码执行结果

 我们可以求得关键路径为0-2-3-6-8-9

四、总结

本文的关键在于拓扑排序的算法实现以及关键路径的求取，特别是关键路径中的各种概念大家一定要理解清楚避免混乱，如果说喜欢本文的话麻烦点个赞

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/258224?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。