数据结构实验六(AOE关键路径详细版)_6 获取aoe网的关键路径

数据结构AOE关键路径，关于这个有些知识点需要涉及，一个是关于拓扑排序，一个是寻找关键路径。下面给出图例。
此次代码每一步相应给出了解释，因为部分算法书上是错误的。
关于拓扑排序就不用多说了，比较简单，下面给出一个AOE的关键路径求法。
当然答主关于图的很多算法有很多，这里就不再一一列出，但注意的是，可以点击此处查看最小生成树的求法与代码。

下面开始我们的数据结构题目
题目描述：按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图1所示AOE网的关键路径。

不过想说句题外话，西安电子科技大学出版的《数据结构》关于此处的算法有错误（要源于课本也要高于课本），我花了一些时间才看出猫腻来，我下面给出了完整的程序并且无错误。

操作提示：一个完整的系统应具有以下功能：
1）输入图的顶点数目.
2）按偏序顺序输入各边顶点及权值.
3）输入(0,0)结束（我这里采取了（0,0,0）的输入）
4）程序会自动计算出关键路径
下面附完整程序

/*
	Jack Leo
	All rights reversed
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

/*创建图的邻接表*/
typedef struct ArcNode{
    int adv;//指向顶点的位置
    struct ArcNode *nextArc;//指向下一条边
    int w;//表示权值
}ArcNode;

typedef struct VNode{
    ArcNode *first;//指向该顶点第一条弧的指针
    string datam; //顶点数据，例如名字
}AdVlist;

typedef struct ALGraph{
    AdVlist vts[500];//顶点向量
    int v,e;
}ALGraph;

/*查找输入的x顶点位置*/
int Find(ALGraph &g,string x){
    for(int i=0;i<g.v;i++){
        if(x==g.vts[i].datam) return i;
    }
    return -1;
}

int ve[500];//全局变量，表示事件最早发生的时间
stack<int> t;//t为返回拓扑序列的栈

/*创建图*/
void Creat(ALGraph &g){
    int mw,edge=0;
    string v1,v2;
    cout<<"输入图的顶点数"<<endl;
    cin>>g.v;
    cout<<"输入图中结点信息"<<endl;
    //输入顶点的信息，并且使指边指向NULL
    for(int i=0;i<g.v;i++){
        cin>>g.vts[i].datam;
        g.vts[i].first=NULL;
    }
    cout<<"输入图中两个顶点（起点和终点）与相应的权值，其中(0,0,0)结束"<<endl;
    while(1){
        cin>>v1>>v2>>mw;
        if(v1=="0"&&v2=="0"&&mw==0) break;
        edge++;
        int j,k;
        j=Find(g,v1);
        k=Find(g,v2);
        ArcNode *p1=new ArcNode;
        //使边p的顶点指向第k个顶点，意思就是第k个顶点为指向量，例如边<i,j>，则j就是这里的k
        p1->adv=k;
        //使边p的权值赋值
        p1->w=mw;
        p1->nextArc=NULL;
        p1->nextArc=g.vts[j].first;
        g.vts[j].first=p1;
    }
    g.e=edge;
}
/*三金编写，版权所有，转载注明*/
/*求各顶点的入度，保存在indegree数组中*/
void FindID(ALGraph g,int indegree[500]){
    int i;
    ArcNode *p;
    for(i=0;i<g.v;i++) indegree[i]=0;//初始化
    for(i=0;i<g.v;i++){
        p=g.vts[i].first;//p是第i个顶点指向的第一条边的指针
        //遍历第i个顶点所有的边，直到指向NULL
        while(p!=NULL){
            indegree[p->adv]++;//边的顶点，就是此时的顶点入度+1
            p=p->nextArc;//遍历
        }
    }
}

/*拓扑排序*/
bool TopOrder(ALGraph g){
    stack<int> s;//s为存放入度为0的顶点的栈
    int count,i,j,k;//count做检验工作，因为入度为0的时候可能会有顶点没有进入，这样做更加保险
    ArcNode *p;
    int indegree[500];//各顶点的入度
    FindID(g,indegree);
    for(i=0;i<g.v;i++){
        if(indegree[i]==0) s.push(i);//使没有入度的点入栈，就是说在拓扑排序中，先寻找入度为0的顶点
    }
    count=0;
    for(i=0;i<g.v;i++){
        ve[i]=0;//初始化最早发生的时间
    }
    while(!s.empty()){
        /*如果栈s非空，那么先出栈并赋值给j，然后使j进入栈t,这样栈t就是拓扑序列，因为s里面的肯定是入度为0的了*/
        j=s.top();
        s.pop();
        t.push(j);
        count++;
        //边p指向顶点j的第一条边
        p=g.vts[j].first;
        while(p!=NULL){
            k=p->adv;
            /*顶点k(就是这条边的指向顶点)度数是否为0，如果不是那么减为0，然后使其入栈*/
            if(!(--indegree[k])) s.push(k);
            //j的最早发生事件+权值是否大于这个顶点的ve，注意一开始ve(0)=0
            if(ve[j]+p->w>ve[k]) ve[k]=ve[j]+p->w;
            p=p->nextArc;
        }
    }
    if(count<g.v) return false;//有回路
    else return true;
}
/*三金编写，版权所有，转载注明*/
/*关键路径算法
    有了最早发生事件了，就是全局变量ve,然后现在要求最晚发生时间了，最后可求出活动的时间
    关键路径就是活动，注意是活动（也就是边）最早和最晚时间发生的活动
*/
bool CriticalPath(ALGraph g){
    ArcNode *p;
    int i,j,k,dut,ei,li;
    int vl[500];//vl为事件，注意不是活动，发生的最晚时间
    //TopOrder(g);
    if(!TopOrder(g)) return false;
    for(i=0;i<g.v;i++) vl[i]=ve[g.v-1];//初始化
    /*按逆拓扑顺序求各顶点的vl*/
    while(!t.empty()){
        j=t.top();
        t.pop();
        p=g.vts[j].first;
        while(p!=NULL){
            k=p->adv;
            dut=p->w;
            if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;
            p=p->nextArc;
        }
    }
    cout<<"关键路径"<<endl;
    cout<<"Initial "<<"End "<<"Weight "<<" el"<<" vl"<<endl;
    for(j=0;j<g.v;j++){
        p=g.vts[j].first;
        while(p!=NULL){
            k=p->adv;
            dut=p->w;
            ei=ve[j];
            li=vl[k]-dut;
            if(ei==li)
                cout<<g.vts[j].datam<<" "<<g.vts[k].datam<<" "<<dut<<endl;
            p=p->nextArc;
        }
    }
    return true;
}


/*三金编写，版权所有，转载注明*/
int main(){
    ALGraph g;
    Creat(g);
    CriticalPath(g);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

下面给出此次程序的运行结果，图例按照上述题目要求的。