筆者從基本儲存方法、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;};  

#p#

　　拓撲排序

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

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;   
}  

#p#

　　總結

　　不同于前面的鏈表和樹，在圖這里，儲存方法不是重點，我們更多的注意力放在了算法上。我在寫程序的時候，也盡量做到了算法和儲存方法無關。然而算法實際上就是現實問題的抽象，如果我們的常識所不及，我們也就沒有辦法來介紹算法，反過來說，幾乎遇不到的問題，我們也不會對它的算法感興趣。

　　因此，在圖的算法里面，由鋪設管道引出了最小生成樹，由提高通信、交通網絡可靠性引出了關節點和重連通分量，由地圖尋徑引出了最短路徑，由工程預算引出了關鍵路徑。這些恐怕是我們能夠理解的全部了，如果再來一個電氣網絡計算，沒點物理知識恐怕是要完。

　　但即使這樣，上面的各個算法仍然離我們很遠，我們大多數人恐怕永遠都不會知道管道是怎么鋪的。我想，這里面除了最短路徑能引起大多數人的興趣之外，其他的就只能走馬觀花的看看罷了。這也使得圖的學習很像“聾子的耳朵”，真正接觸到圖的用途的人不多，并且即使用到圖，也僅僅是個別的算法。

　　正像數據結構教學的通病一樣，學無所用常常導致學無所成，前面的鏈表、樹好歹還能做點什么東西出來，到了圖這里，除了做個導游系統，我們也做不出別的什么了。寫到這里很無奈，但我也只能是無奈……

　　那么，學完了圖，我們應該掌握什么呢，是上面零散的算法嗎?我的看法是，不是。我覺得我們更應該知道那些算法是怎么“創造”出來的，如果遇到了類似的問題，能不能“派生”出新的算法。因此，我覺得《數據結構算法與應用-C++語言描述》這本書，將圖的最小生成樹、最短路徑、拓撲排序算法放到了貪婪算法里講解，是一種更為合理的安排。

【編輯推薦】

1. 經典四講貫通C++排序之一 插入排序
2. c++編程常用工具
3. 給C++初學者的50個忠告
4. c++最基礎的20條規則
5. 程序員必看 c++筆試題匯總