六講貫通C++圖的應用之六 活動網絡(AOV、AOE)(1)

筆者從基本儲存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動網絡(AOV、AOE)六個方面詳細介紹C++圖的應用。我們已經前面的文章介紹了前五個方面的知識，今天我們介紹最後一個——活動網絡(AOV、AOE)。

活動網絡(AOV、AOE)

這部分是和工程相關的，也就是說，當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 name, class dist>   
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 name, class dist> class ActivityNetwork;   
template <class name, class dist> class Link   
{friend class ActivityNetwork;};   
template <class name, class dist, class mem> class Network   
{ friend class ActivityNetwork;};