六講貫通C++圖的應用之三 無向圖(1)

筆者從基本儲存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動網絡(AOV、AOE)六個方面詳細介紹C++圖的應用。之前我們已經介紹了基本存儲方法、DFS和BFS，這篇我們繼續介紹無向圖。

無向圖

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

無向圖類

template <class name, class dist, class mem>  
class Graph : public Network  
{  
public:  
Graph() {}  
Graph(dist maxdist) : Network (maxdist) {}  
bool insertE(name v1, name v2, dist cost)  
{  
if (Network::insertE(v1, v2, cost))  
return Network::insertE(v2, v1, cost);  
return false;  
}  
}; 

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

連通分量

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

void components()  
{  
visited = new bool[vNum()]; int i, j = 0;  
for (i = 0; i < vNum(); i++) visited[i] = false;  
cout << "Components:" << endl;  
for (i = 0; i < vNum(); i++)  
{  
if (!visited[i]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }  
}  
delete []visited;  
}