六讲贯通C++图的应用之六 活动网络(AOV、AOE)(1)(2)

拓扑排序

这个算法很精巧，避免了对已经排好序的顶点的再次扫描，另外，殷版上用计数数组来充当栈的方法也很巧妙。算法的说明参阅相关的教科书，不再赘述。

bool TopoSort()   
{   
initialize(); int i, top = -1;   
for (i = 0; i < N; i++) if (!count[i]) { count[i] = top; top = i; }   
for (i = 0; i < N; i++) //TopoSort Start   
{   
if (top == -1) return false;   
result[i] = top; top = count[top];   
for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)   
if (!--count[iter->vID]) { count[iter->vID] = top; top = iter->vID; }   
}   
return true;   
}  

由于public数据成员out和private数据成员result指向同一个数组，在类的外面可以通过out来得到排序结果，只是不能改变(当然，非要改变const数据也不是没有办法)。下面是测试程序，数据来自殷版：

#include    
using namespace std;   
#include "ActivityNetwork.h"   
int main()   
{   
Network<int, int, Link<int, int> > a;   
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);a.insertV(5);   
a.insertE(0,3,1);a.insertE(0,1,1);a.insertE(1,5,1);a.insertE(2,1,1);   
a.insertE(2,5,1);a.insertE(4,0,1);a.insertE(4,1,1);a.insertE(4,5,1);   
ActivityNetwork<int, int> b(&a);   
if (b.TopoSort()) for (int i = 0; i < a.vNum(); i++) cout << b.out[i] << ' ';   
return 0;   
}  

关键路径

有了拓扑排序的结果，这个程序就比较好写了，那些所谓的“技巧”就不用了，如下的程序，很直白，算法说明请参考教科书。

bool CriPath()   
{   
if (!TopoSort()) return false; int i; iterator iter; CA.clear();   
dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早开始时间，Vl最迟开始时间   
for (i = 0; i < N; i++) Ve[i] = 0;//Ve初始化   
for (i = 0; i < N; i++)//按拓扑顺序计算Ve   
for (iter = begin(result[i]); iter != end(result[i]); iter++)   
if (Ve[result[i]]+iter->cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;   
for (i = 0; i < N; i++) Vl[i] = Ve[N - 1];//Vl初始化   
for (i = N - 2; i >= 0; i--)//按逆拓扑顺序计算Vl   
for (iter = begin(result[i]); iter != end(result[i]); iter++)   
if (Vl[iter->vID]-iter->cost < Vl[result[i]]) Vl[result[i]] = Vl[iter->vID] - iter->cost;   
for (i = 0; i < N; i++)//计算各个活动的最早开始时间和最迟开始时间   
for (iter = begin(i); iter != end(i); iter++)   
if (Ve[i] == Vl[iter->vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));   
return true;   
}  

同样的在类的外面可以通过outCriAct得到结果，是一个const引用。如下的测试程序，数据来自殷版：

#include    
using namespace std;   
#include "ActivityNetwork.h"   
int main()   
{   
Network<int, int, Link<int, int> > a;   
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);   
a.insertV(5); a.insertV(6);a.insertV(7);a.insertV(8);   
a.insertE(0,1,6);a.insertE(0,2,4);a.insertE(0,3,5);   
a.insertE(1,4,1);a.insertE(2,4,1);a.insertE(3,5,2);   
a.insertE(4,6,9);a.insertE(4,7,7);a.insertE(5,7,4);   
a.insertE(6,8,2);a.insertE(7,8,4);   
ActivityNetwork<int, int> b(&a);   
if (b.CriPath())   
for (int j = 0; j < b.outCriAct.size(); j++)   
cout <<'<'<',' << a.getV(b.outCriAct[j].d) << '>' << ' ';   
return 0;   
}