这部分是和工程相关的，也就是说，当AOV、AOE很复杂的时候，才能显示出这部分的价值——简单的话，手工都要比程序快，输入数据那段时间手工结果就出来了。我也没什么例子好举，总给我一种没底气的感觉，勉为其难的把程序写完就算完事吧。和前边的相比，这部分专业了一点，换而言之，不是每个人都感兴趣，不想看就跳过去吧。 准备工作 活动网络主要有两个算法，拓扑排序和求关键路径，后者以前者为基础。仿照上篇，另外构造一个“算法类”，需要算法时，将图绑定到算法上。 #include "Network.h" #define iterator list<Link<name, dist>::edge>::iterator #define begin(i) G->data.vertices[i].e->begin() #define end(i) G->data.vertices[i].e->end() struct CriAct { CriAct() {} CriAct(int source, int dest) : s(source), d(dest) {} int s, d; }; template <class name, class dist> class ActivityNetwork { public: ActivityNetwork(Network<name, dist, Link<name, dist> >* G) : G(G), N(G->vNum()), outCriAct(CA) { count = new int[N]; result = new int[N]; } ~ActivityNetwork() { delete []count; delete []result; } const vector<CriAct>& outCriAct; const int* out; private: void initialize() { for (int j = 0; j < N; j++) count[j] = 0; for (int i = 0; i < N; i++) { for (iterator iter = begin(i); iter != end(i); iter++) count[iter->vID]++; } out = result; } Network<name, dist, Link<name, dist> >* G; vector<CriAct> CA; int N, *count, *result; }; 因为AOV和AOE的边都不会太多（想象一下边多的情况，那事件就都是鸡毛蒜皮了），所以储存结构直接选择了邻接表。并且为了体现邻接表的优势，需要直接操作私有数据，因此要把这个类声明为Link类和Network类的友元，另外由于这个类在后面，所以需要前视声明。具体如下： template <class name, class dist> class ActivityNetwork; template <class name, class dist> class Link {friend class ActivityNetwork<name, dist>;}; template <class name, class dist, class mem> class Network { friend class ActivityNetwork<name, dist>;}; 拓扑排序 这个算法很精巧，避免了对已经排好序的顶点的再次扫描，另外，殷版上用计数数组来充当栈的方法也很巧妙。算法的说明参阅相关的教科书，不再赘述。 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 <iostream> 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 <iostream> 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].s) << ',' << a.getV(b.outCriAct[j].d) << '>' << ' '; return 0; }
评论