這部分是和工程相關的，也就是說，當AOV、AOE很復雜的時候，才能顯示出這部分的價值——簡單的話，手工都要比程序快，輸入數據那段時間手工結果就出來了。我也沒什么例子好舉，總給我一種沒底氣的感覺，勉為其難的把程序寫完就算完事吧。和前邊的相比，這部分專業了一點，換而言之，不是每個人都感興趣，不想看就跳過去吧。
　
　　準備工作

　　活動網絡主要有兩個算法，拓撲排序和求關鍵路徑，后者以前者為基礎。仿照上篇，另外構造一個“算法類”，需要算法時，將圖綁定到算法上。

#include "Network.h"
#define iterator list::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 ActivityNetwork
{
public:
ActivityNetwork(Network >* G) : G(G), N(G->vNum()), outCriAct(CA)
{
count = new int[N]; result = new int[N];
}

~ActivityNetwork()
{
delete []count; delete []result;
}
const vector& 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 >* G;
vector CA;
int N, *count, *result;
};

　　因為AOV和AOE的邊都不會太多（想象一下邊多的情況，那事件就都是雞毛蒜皮了），所以儲存結構直接選擇了鄰接表。并且為了體現鄰接表的優勢，需要直接操作私有數據，因此要把這個類聲明為Link類和Network類的友元，另外由于這個類在后面，所以需要前視聲明。具體如下：

template class ActivityNetwork;
template class Link
{friend class ActivityNetwork;};
template class Network
{ friend class ActivityNetwork;};

　　拓撲排序

　　這個算法很精巧，避免了對已經排好序的頂點的再次掃描，另外，殷版上用計數數組來充當棧的方法也很巧妙。算法的說明參閱相關的教科書，不再贅述。

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 > 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 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 > 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 b(&a);

if (b.CriPath())
for (int j = 0; j < b.outCriAct.size(); j++)
cout <<'<'<' << ' ';
return 0;
}