日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
六講貫通C++圖的應(yīng)用之三無向圖

　　筆者從基本儲(chǔ)存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動(dòng)網(wǎng)絡(luò)(AOV、AOE)六個(gè)方面詳細(xì)介紹C++圖的應(yīng)用。之前我們已經(jīng)介紹了基本存儲(chǔ)方法、DFS和BFS，這篇我們繼續(xù)介紹無向圖。

　　無向圖

　　要是在紙上隨便畫畫，或者只是對(duì)圖做點(diǎn)示范性的說明，大多數(shù)人都會(huì)選擇無向圖。然而在計(jì)算機(jī)中，無向圖卻是按照有向圖的方法來儲(chǔ)存的——存兩條有向邊。實(shí)際上，當(dāng)我們說到無向的時(shí)候，只是忽略方向——在紙上畫一條線，難不成那線“嗖”的就出現(xiàn)了，不是從一頭到另一頭畫出來的? 無向圖有幾個(gè)特有的概念，連通分量、關(guān)節(jié)點(diǎn)、最小生成樹。下面將分別介紹，在此之前，先完成無向圖類的基本操作。

　　無向圖類

 
 
 
    
  
  
  
  1. template   
    2.   
  
  
  2. class Graph : public Network   
    3.   
  
  
  3. {  
    4.   
  
  
  4. public:  
    5.   
  
  
  5. Graph() {}  
    6.   
  
  
  6. Graph(dist maxdist) : Network  (maxdist) {}   
    7.   
  
  
  7. bool insertE(name v1, name v2, dist cost)  
    8.   
  
  
  8. {  
    9.   
  
  
  9. if (Network ::insertE(v1, v2, cost))   
    10.   
  
  
  10. return Network ::insertE(v2, v1, cost);   
    11.   
  
  
  11. return false;  
    12.   
  
  
  12. }  
    13.   
  
  
  13. }; 
    14.

　　僅僅是添加邊的時(shí)候，再添加一條反向邊，很簡單。

　　連通分量

這是無向圖特有的，有向圖可要復(fù)雜多了(強(qiáng)、單、弱連通)，原因就是無向圖的邊怎么走都行，有向圖的邊好像掉下無底深淵就再也爬不上來了。有了DFS，求連通分量的算法就變得非常簡單了——對(duì)每個(gè)沒有訪問的頂點(diǎn)調(diào)用DFS就可以了。

 
 
 
    
  
  
  
  1. void components()  
    2.   
  
  
  2. {  
    3.   
  
  
  3. visited = new bool[vNum()]; int i, j = 0;  
    4.   
  
  
  4. for (i = 0; i < vNum(); i++) visited[i] = false;  
    5.   
  
  
  5. cout << "Components:" << endl;  
    6.   
  
  
  6. for (i = 0; i < vNum(); i++)  
    7.   
  
  
  7. {  
    8.   
  
  
  8. if (!visited[i]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }  
    9.   
  
  
  9. }  
    10.   
  
  
  10. delete []visited;  
    11.   
  
  
  11. } 
    12.

#p#

　　關(guān)節(jié)點(diǎn)

　　下定義是人們認(rèn)識(shí)事物的一個(gè)方法，因?yàn)楦拍钍沟萌藗兡軌騾^(qū)分事物——關(guān)于這個(gè)還有個(gè)絕對(duì)的運(yùn)動(dòng)和相對(duì)的靜止的哲學(xué)觀點(diǎn)(河水總在流，但是長江還叫長江，記得那個(gè)著名的“不可能踏進(jìn)同一條河里”嗎?)因此，能否有個(gè)準(zhǔn)確的概念往往是一門學(xué)科發(fā)展程度的標(biāo)志，而能否下一個(gè)準(zhǔn)確的定義反映了一個(gè)人的思維能力。說這么多廢話，原因只有一個(gè)，我沒搞清楚什么叫“關(guān)節(jié)點(diǎn)”——參考書有限，不能仔細(xì)的考究了，如有誤解，還望指正。

　　嚴(yán)版是這么說的：如果刪除某個(gè)頂點(diǎn)，將圖的一個(gè)連通分量分割成兩個(gè)或兩個(gè)以上的連通分量，稱該頂點(diǎn)為關(guān)節(jié)點(diǎn)。——雖然沒有提到圖必須是無向的，但是提到了連通分量已經(jīng)默認(rèn)是無向圖了。

　　殷版是這么說的：在一個(gè)無向連通圖中，……(余下同嚴(yán)版)。

　　問題出來了，非連通圖是否可以討論含有關(guān)節(jié)點(diǎn)?我們是否可以說某個(gè)連通分量中含有關(guān)節(jié)點(diǎn)?遺憾的是，嚴(yán)版留下這個(gè)問題之后，在后面給出的算法是按照連通圖給的，這樣當(dāng)圖非連通時(shí)結(jié)果就是錯(cuò)的。殷版更是滑頭，只輸出重連通分量，不輸出關(guān)節(jié)點(diǎn)，自己雖然假定圖是連通的，同樣沒有連通判斷。

　　翻翻離散數(shù)學(xué)吧，結(jié)果沒找到什么“關(guān)節(jié)點(diǎn)”，只有“割點(diǎn)”，是這樣的：一個(gè)無向連通圖，如果刪除某個(gè)頂點(diǎn)后，變?yōu)榉沁B通圖，該頂點(diǎn)稱為割點(diǎn)。權(quán)當(dāng)“割點(diǎn)”就是“關(guān)節(jié)點(diǎn)”，那么算法至少也要先判斷是否連通吧?可是書上都直接當(dāng)連通的了……

　　關(guān)于算法不再細(xì)說，書上都有。下面的示例，能輸出每個(gè)連通分量的“關(guān)節(jié)點(diǎn)”(是不是可以這樣叫，我也不清楚)。dfn儲(chǔ)存的是每個(gè)頂點(diǎn)的訪問序號(hào)，low是深度優(yōu)先生成樹上每個(gè)非葉子頂點(diǎn)的子女通過回邊所能到達(dá)的頂點(diǎn)最小的訪問序號(hào)。把指向雙親的邊也當(dāng)成回邊并不影響判斷，因此不必特意區(qū)分，殷版顯式區(qū)分了，屬于畫蛇添足。這樣一來，if (low[n] >= dfn[i]) cout << getV(i);這個(gè)輸出關(guān)節(jié)點(diǎn)的判斷中的>=就顯得很尷尬了，因?yàn)橹荒艿扔诓豢赡艽笥?。還要注意的是，生成樹的根(DFS的起始點(diǎn))是單獨(dú)判斷的。

 
 
 
    
  
  
  
  1. void articul()  
    2.   
  
  
  2. {  
    3.   
  
  
  3. dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;  
    4.   
  
  
  4. for(i = 0; i < vNum(); i++) dfn[i] = low[i] = 0;//初始化  
    5.   
  
  
  5. for (i = 0; i < vNum(); i++)  
    6.   
  
  
  6. {  
    7.   
  
  
  7. if (!dfn[i])  
    8.   
  
  
  8. {  
    9.   
  
  
  9. cout << '(' << ++j << ')'; dfn[i] = low[i] = count = 1;  
    10.   
  
  
  10. if ((n = nextV(i)) != -1) articul(n); bool out = false;//訪問樹根  
    11.   
  
  
  11. while ((n = nextV(i, n)) != -1)  
    12.   
  
  
  12. {  
    13.   
  
  
  13. if (dfn[n]) continue;  
    14.   
  
  
  14. if (!out) { cout << getV(i); out = true; }//樹根有不只一個(gè)子女  
    15.   
  
  
  15. articul(n);//訪問其他子女  
    16.   
  
  
  16. }  
    17.   
  
  
  17. cout << endl;  
    18.   
  
  
  18. }  
    19.   
  
  
  19. }  
    20.   
  
  
  20. delete []dfn; delete []low;  
    21.   
  
  
  21. }  
    22.   
  
  
  22.  
    23.   
  
  
  23. private:  
    24.   
  
  
  24. void articul(int i)  
    25.   
  
  
  25. {  
    26.   
  
  
  26. dfn[i] = low[i] = ++count;  
    27.   
  
  
  27. for (int n = nextV(i); n != -1; n = nextV(i, n))  
    28.   
  
  
  28. {  
    29.   
  
  
  29. if (!dfn[n])  
    30.   
  
  
  30. {  
    31.   
  
  
  31. articul(n);  
    32.   
  
  
  32. if (low[n] < low[i]) low[i] = low[n];  
    33.   
  
  
  33. if (low[n] >= dfn[i]) cout << getV(i);//這里只可能＝  
    34.   
  
  
  34. }  
    35.   
  
  
  35. else if (dfn[n] < low[i]) low[i] = dfn[n];//回邊判斷  
    36.   
  
  
  36. }  
    37.   
  
  
  37. }  
    38.   
  
  
  38. int *dfn, *low, count; 
    39.

網(wǎng)頁題目：六講貫通C++圖的應(yīng)用之三無向圖
當(dāng)前URL：http://www.5511xx.com/article/djdcpcs.html