自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

六講貫通C++圖的應(yīng)用之六 活動(dòng)網(wǎng)絡(luò)(AOV、AOE)

作者：happycock
開發(fā) 后端
圖的應(yīng)用恐怕是C++所有數(shù)據(jù)結(jié)構(gòu)中最寬泛的了，本次六講筆者從基本儲(chǔ)存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動(dòng)網(wǎng)絡(luò)(AOV、AOE)六個(gè)方面詳細(xì)介紹圖的應(yīng)用。本文是這次系列文章的最后一篇，主要介紹活動(dòng)網(wǎng)絡(luò)(AOV、AOE)。

 

　　筆者從基本儲(chǔ)存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動(dòng)網(wǎng)絡(luò)(AOV、AOE)六個(gè)方面詳細(xì)介紹C++圖的應(yīng)用。我們已經(jīng)前面的文章介紹了前五個(gè)方面的知識(shí)，今天我們介紹***一個(gè)——活動(dòng)網(wǎng)絡(luò)(AOV、AOE)。

　　活動(dòng)網(wǎng)絡(luò)(AOV、AOE)

　　這部分是和工程相關(guān)的，也就是說，當(dāng)AOV、AOE很復(fù)雜的時(shí)候，才能顯示出這部分的價(jià)值——簡(jiǎn)單的話，手工都要比程序快，輸入數(shù)據(jù)那段時(shí)間手工結(jié)果就出來了。我也沒什么例子好舉，總給我一種沒底氣的感覺，勉為其難的把程序?qū)懲昃退阃晔掳?。和前邊的相比，這部分專業(yè)了一點(diǎn)，換而言之，不是每個(gè)人都感興趣，不想看就跳過去吧。

　　準(zhǔn)備工作

　　活動(dòng)網(wǎng)絡(luò)主要有兩個(gè)算法，拓?fù)渑判蚝颓箨P(guān)鍵路徑，后者以前者為基礎(chǔ)。仿照上篇，另外構(gòu)造一個(gè)“算法類”，需要算法時(shí)，將圖綁定到算法上。

  1. #include "Network.h"   
  2. #define iterator list::edge>::iterator   
  3. #define begin(i) G->data.vertices[i].e->begin()   
  4. #define end(i) G->data.vertices[i].e->end()   
  5. struct CriAct   
  6. {   
  7. CriAct() {}   
  8. CriAct(int source, int dest) : s(source), d(dest) {}   
  9. int s, d;   
  10. };   
  11. template <class name, class dist>   
  12. class ActivityNetwork   
  13. {   
  14. public:   
  15. ActivityNetwork(Network >* G) : G(G), N(G->vNum()), outCriAct(CA)   
  16. {   
  17. count = new int[N]; result = new int[N];   
  18. }   
  19. ~ActivityNetwork()   
  20. {   
  21. delete []count; delete []result;   
  22. }   
  23. const vector& outCriAct;   
  24. const int* out;   
  25. private:   
  26. void initialize()   
  27. {   
  28. for (int j = 0; j < N; j++) count[j] = 0;   
  29. for (int i = 0; i < N; i++)   
  30. {   
  31. for (iterator iter = begin(i); iter != end(i); iter++) count[iter->vID]++;   
  32. }   
  33. out = result;   
  34. }   
  35. Network >* G;   
  36. vector CA;   
  37. int N, *count, *result;   
  38. };  

　　因?yàn)锳OV和AOE的邊都不會(huì)太多(想象一下邊多的情況，那事件就都是雞毛蒜皮了)，所以儲(chǔ)存結(jié)構(gòu)直接選擇了鄰接表。并且為了體現(xiàn)鄰接表的優(yōu)勢(shì)，需要直接操作私有數(shù)據(jù)，因此要把這個(gè)類聲明為L(zhǎng)ink類和Network類的友元，另外由于這個(gè)類在后面，所以需要前視聲明。具體如下：

  1. template <class name, class dist> class ActivityNetwork;   
  2. template <class name, class dist> class Link   
  3. {friend class ActivityNetwork;};   
  4. template <class name, class dist, class mem> class Network   
  5. { friend class ActivityNetwork;};  

#p#

　　拓?fù)渑判?/STRONG>

　　這個(gè)算法很精巧，避免了對(duì)已經(jīng)排好序的頂點(diǎn)的再次掃描，另外，殷版上用計(jì)數(shù)數(shù)組來充當(dāng)棧的方法也很巧妙。算法的說明參閱相關(guān)的教科書，不再贅述。

  1. bool TopoSort()   
  2. {   
  3. initialize(); int i, top = -1;   
  4. for (i = 0; i < N; i++) if (!count[i]) { count[i] = top; top = i; }   
  5. for (i = 0; i < N; i++) //TopoSort Start   
  6. {   
  7. if (top == -1) return false;   
  8. result[i] = top; top = count[top];   
  9. for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)   
  10. if (!--count[iter->vID]) { count[iter->vID] = top; top = iter->vID; }   
  11. }   
  12. return true;   
  13. }  

　　由于public數(shù)據(jù)成員out和private數(shù)據(jù)成員result指向同一個(gè)數(shù)組，在類的外面可以通過out來得到排序結(jié)果，只是不能改變(當(dāng)然，非要改變const數(shù)據(jù)也不是沒有辦法)。下面是測(cè)試程序，數(shù)據(jù)來自殷版：

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

　　關(guān)鍵路徑

　　有了拓?fù)渑判虻慕Y(jié)果，這個(gè)程序就比較好寫了，那些所謂的“技巧”就不用了，如下的程序，很直白，算法說明請(qǐng)參考教科書。

  1. bool CriPath()   
  2. {   
  3. if (!TopoSort()) return false; int i; iterator iter; CA.clear();   
  4. dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早開始時(shí)間，Vl最遲開始時(shí)間   
  5. for (i = 0; i < N; i++) Ve[i] = 0;//Ve初始化   
  6. for (i = 0; i < N; i++)//按拓?fù)漤樞蛴?jì)算Ve   
  7. for (iter = begin(result[i]); iter != end(result[i]); iter++)   
  8. if (Ve[result[i]]+iter->cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;   
  9. for (i = 0; i < N; i++) Vl[i] = Ve[N - 1];//Vl初始化   
  10. for (i = N - 2; i >= 0; i--)//按逆拓?fù)漤樞蛴?jì)算Vl   
  11. for (iter = begin(result[i]); iter != end(result[i]); iter++)   
  12. if (Vl[iter->vID]-iter->cost < Vl[result[i]]) Vl[result[i]] = Vl[iter->vID] - iter->cost;   
  13. for (i = 0; i < N; i++)//計(jì)算各個(gè)活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間   
  14. for (iter = begin(i); iter != end(i); iter++)   
  15. if (Ve[i] == Vl[iter->vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));   
  16. return true;   
  17. }  

　　同樣的在類的外面可以通過outCriAct得到結(jié)果，是一個(gè)const引用。如下的測(cè)試程序，數(shù)據(jù)來自殷版：

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

#p#

　　總結(jié)

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

　　因此，在圖的算法里面，由鋪設(shè)管道引出了最小生成樹，由提高通信、交通網(wǎng)絡(luò)可靠性引出了關(guān)節(jié)點(diǎn)和重連通分量，由地圖尋徑引出了最短路徑，由工程預(yù)算引出了關(guān)鍵路徑。這些恐怕是我們能夠理解的全部了，如果再來一個(gè)電氣網(wǎng)絡(luò)計(jì)算，沒點(diǎn)物理知識(shí)恐怕是要完。

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

　　正像數(shù)據(jù)結(jié)構(gòu)教學(xué)的通病一樣，學(xué)無所用常常導(dǎo)致學(xué)無所成，前面的鏈表、樹好歹還能做點(diǎn)什么東西出來，到了圖這里，除了做個(gè)導(dǎo)游系統(tǒng)，我們也做不出別的什么了。寫到這里很無奈，但我也只能是無奈……

　　那么，學(xué)完了圖，我們應(yīng)該掌握什么呢，是上面零散的算法嗎?我的看法是，不是。我覺得我們更應(yīng)該知道那些算法是怎么“創(chuàng)造”出來的，如果遇到了類似的問題，能不能“派生”出新的算法。因此，我覺得《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語(yǔ)言描述》這本書，將圖的最小生成樹、最短路徑、拓?fù)渑判蛩惴ǚ诺搅素澙匪惴ɡ镏v解，是一種更為合理的安排。

【編輯推薦】

  1. 經(jīng)典四講貫通C++排序之一 插入排序
  2. c++編程常用工具
  3. 給C++初學(xué)者的50個(gè)忠告
  4. c++最基礎(chǔ)的20條規(guī)則
  5. 程序員必看 c++筆試題匯總
責(zé)任編輯：韓亞珊 來源： 天極網(wǎng)
AOVAOE活動(dòng)網(wǎng)絡(luò)C++
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)