上一篇文章講了圖的有關概念以及圖的兩種存儲方式，
點選打開連結
接下來我們一起學習圖的兩種周遊及最小生成樹的實作。
一、圖的周遊
1、廣度優先周遊（Breadth First Search, BFS）
廣度優先搜尋類似于樹的層序周遊，看一個例子：
假設我們都從節點0開始周遊，無向圖周遊順序為0,3,4,1,2,，有向圖周遊順序為0,3,4,1,2。
下面是實作的代碼，需要借助隊列來完成：
// 圖的廣度優先周遊
void BFS(const V& v)
{
queue<int> q;
//标記是否已經周遊，周遊過為true
vector<bool> visited(_v.size(), false);
size_t index = GetIndexOfV(v);
q.push(index);
_BFS(q, visited);
//避免漏掉與其他頂點無關的點
for (size_t i = 0; i < _v.size(); i++)
{
if (visited[i] == false)
{
q.push(i);
_BFS(q, visited);
}
}
cout << endl;
}
void _BFS(queue<int>& q, vector<bool>& visited)
{
while (!q.empty())
{
size_t index = q.front();
q.pop();
if (visited[index] == true)
continue;
visited[index] = true;
cout << _v[index] << " ";
pNode pCur = _linkEdges[index];
while (pCur)
{
if (visited[pCur->_dst] == false)
q.push(pCur->_dst);
pCur = pCur->_pNext;
}
}
} 2、深度優先周遊
深度優先周遊相當于一條路走到黑的道理，還是上面的例子：
假設我們都從節點0開始周遊，無向圖周遊順序為0,3,1,4,2，有向圖周遊順序為0,3,1,2,4。
代碼如下：
// 圖的深度優先周遊
void DFS(const V& v)
{
size_t index = GetDevOfV(v);
vector<bool> visited(_v.size(), false);
_DFS(index, visited);
for (size_t i = 0; i < _v.size(); i++)
{
if (visited[i] == false)
_DFS(i, visited);
}
cout << endl;
}
void _DFS(int index, vector<bool>& visited)
{
cout << _v[index] << " ";
visited[index] = true;
pNode pCur = _linkEdges[index];
while (pCur)
{
if (visited[pCur->_dst] == false)
_DFS(pCur->_dst, visited);
pCur = pCur->_pNext;
}
} 二、最小生成樹
連通圖中的每一棵生成樹，都是原圖的一個極大無環子圖，即：從其中删去任何一條邊，生成樹就不在連通；反之，在其中引入任何一條新邊，都會形成一條回路。
若連通圖由n個頂點組成，則其生成樹必含n個頂點和n-1條邊。是以構造最小生成樹的準則有三 條：
（1）. 隻能使用圖中的邊來構造最小生成樹
（2）. 隻能使用恰好n-1條邊來連接配接圖中的n個頂點
（3）. 選用的n-1條邊不能構成回路
構造最小生成樹的方法：Kruskal算法和Prim算法。這兩個算法都采用了逐漸求解的貪心政策。
注：貪心算法：是指在問題求解時，總是做出目前看起來最好的選擇。也就是說貪心算法做出的不是整體最優的的選擇，而是某種意義上的局部最優解。貪心算法不是對所有的問題都能得到整體最優解。
我們了解一下兩種算法。
1、Kruskal算法
任給一個有n個頂點的連通網絡N={V, E}，首先構造一個由這n個頂點組成、不含任何邊的圖G= {V, NU LL }，其中每個頂點自成一個連通分量，不斷從E中取出權值最小的一條邊(若有多條任取其一) ，若該邊的兩個頂點來自不同的連通分量，則将此邊加入到G中。如此重複，直到所有頂點在同一個連通分量上為止。
核心：每次疊代時，選出一條具有最小權值，且兩端點不在同一連通分量上的邊，加入生成樹。
舉例說明一下：
步驟如下：
（1）建立一個圖，隻有圖的頂點，沒有邊，且 我們有5個頂點，是以需要4（n-1)條邊
（2）将原圖中邊的權值，從小到大排序
（3）利用之前寫過的 并查集，如果需要連接配接的頂點不在已經連通的集合裡，那麼将該邊加到新圖中；
否則，繼續看下一條邊。
可以參考之前文章的并查集。
具體實作：
// 最小生成樹---克魯斯卡爾算法；
typedef Graph<V, W, IsDirect> Self;
typedef Node LinkEdge;
Self Kruskal()
{
Self g; //建立一個圖
g._v = _v; //
g._linkEdges.resize(_v.size());
vector<LinkEdge*> edges;
for (size_t i = 0; i > _v.size(); i++)
{
LinkEdge* pCur = _linkEdges[i];
while (pCur)
{
if (IsDirect || (!IsDirect&&pCur->_src < pCur->_dst)) //儲存邊的權值
edges.push_back(pCur);
pCur = pCur->_pNext;
}
}
class Compare
{
public:
bool operator()(const LinkEdge* left, const LinkEdge* right)
{
return left->_weight < right->_weight;
}
};
sort(edges.begin(), edges.end(), Compare());
size_t count = _v.size() - 1;//從前往後取n-1條邊
UnionFind u(_v.size());
for (size_t i = 0; i < edges.size(); i++)
{
LinkEdge* pCur = edges[i];
size_t srcRoot = u.FindRoot(pCur->_src);
size_t dstRoot = u.FindRoot(pCur->_dst);
if (srcRoot != dstRoot) //兩個節點不在一個集合，加邊
{
g.AddEdge(pCur->_src, pCur->_dst, pCur->_weight);
if (!IsDirect) //有向圖
g.AddEdge(pCur->_dst, pCur->_src, pCur->_weight);
u.Union(pCur->_src, pCur->_dst);//合并
count--;
if (count == 0)
break;
}
}
if (count > 0)
cout << "最小生成樹非法" << endl;
return g;
} 2、Prim算法
普裡姆算法
（Prim算法），圖論中的一種算法，可在權重連通圖裡搜尋
最小生成樹 。
即由此算法搜尋到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；并在1957年由美國計算機科學家羅伯特·普裡姆（英語：Robert C. Prim）獨立發現；1959年， 艾茲格·迪科斯徹 再次發現了該算法。是以，在某些場合，普裡姆算法又被稱為DJP算法、亞爾尼克算法或普裡姆－亞爾尼克算法。
1).輸入：一個權重連通圖，其中頂點集合為V，邊集合為E；
2).初始化：V
new = {x}，其中x為集合V中的任一節點（起始點），E new = {},為空；
3).重複下列操作，直到V
new = V。
a.在集合E中選取權值最小的邊<u, v>，其中u為集合V
new中的元素，而v不在V new集合當中，并且v∈V（如果存在有多條滿足前 述條件即具有相同權值的邊，則可任意選取其中之一）；
b.将v加入集合V
new中，将<u, v>邊加入集合E new中；