六講貫通C++圖的應用之四 最小生成樹(1)

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

最小生成樹

說人是最難伺候的，真是一點不假。上面剛剛為了“提高可靠性”添加了幾條多余的邊，這會兒又來想辦法怎麼能以最小的代價把所有的頂點都連起來。可能正是人的這種精神才使得人類能夠進步吧——看著現在3GHz的CPU真是眼紅啊，我還在受500MHz的煎熬，然後再想想8086……

正如圖的基本元素是頂點和邊，從這兩個方向出發，就能得到兩個算法——Kruskal算法(從邊出發)、Prim算法(從頂點出發)。據說還有別的方法，恕我參考資料有限，不能詳查。

最小生成樹的儲存

顯然用常用的樹的儲存方法來儲存沒有必要，雖然名曰“樹”，實際上，這裡誰是誰的“祖先”、“子孫”並不重要。因此，用如下的MSTedge結構數組來儲存就可以了。

template <class dist>   
class MSTedge   
{   
public:   
MSTedge() {}   
MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}   
int v1, v2;   
dist cost;   
bool operator > (const MSTedge& v2) { return (cost > v2.cost); }   
bool operator < (const MSTedge& v2) { return (cost < v2.cost); }   
bool operator == (const MSTedge& v2) { return (cost == v2.cost); }   
};  

Kruskal算法

最小生成樹直白的講就是，挑選N-1條不產生回路最短的邊。Kruskal算法算是最直接的表達了這個思想——在剩余邊中挑選一條最短的邊，看是否產生回路，是放棄，不是選定然後重復這個步驟。說起來倒是很簡單，做起來就不那麼容易了——判斷是否產生回路需要並查集，在剩余邊中找一條最短的邊需要最小堆(並不需要對所有邊排序，所以堆是最佳選擇)。

Kruskal算法的復雜度是O(eloge)，當e接近N^2時，可以看到這個算法不如O(N^2)的Prim算法，因此，他適合於稀疏圖。而作為稀疏圖，通常用鄰接表來儲存比較好。另外，對於鄰接矩陣儲存的圖，Kruskal算法比Prim算法占不到什麼便宜(初始還要掃描N^2條“邊”)。因此，最好把Kruskal算法放在Link類裡面。

template <class name, class dist> int Link::MinSpanTree(MSTedge* a)   
{   
MinHeap > E; int i, j, k, l = 0;   
MFSets V(vNum); list::iterator iter;   
for (i = 0; i < vNum; i++)   
for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++)   
E.insert(MSTedge(i, iter->vID, iter->cost));//建立邊的堆   
for (i = 0; i < eNum && l < vNum; i++)//Kruskal Start   
{   
j = V.find(E.top().v1); k = V.find(E.top().v2);   
if (j != k) { V.merge(j, k); a[l] = E.top(); l++; }   
E.pop();   
}   
return l;   
}  

下面是堆和並查集的實現

#ifndef Heap_H   
#define Heap_H   
#include    
using namespace std;   
#define minchild(i) (heap[i*2+1] 
template <class T>   
class MinHeap   
{   
public:   
void insert(const T& x) { heap.push_back(x); FilterUp(heap.size()-1); }   
const T& top() { return heap[0]; }   
void pop() { heap[0] = heap.back(); heap.pop_back(); FilterDown(0); }   
private:   
void FilterUp(int i)   
{   
for (int j = (i - 1) / 2; j >= 0 && heap[j] > heap[i]; i = j, j = (i - 1) / 2)   
swap(heap[i], heap[j]);   
}   
void FilterDown(int i)   
{   
for (int j = minchild(i); j < heap.size() && heap[j] < heap[i]; i = j, j = minchild(i))   
swap(heap[i], heap[j]);   
}   
vector heap;   
};   
#endif   
 
#ifndef MFSets_H   
#define MFSets_H   
class MFSets   
{   
public:   
MFSets(int maxsize) : size(maxsize)   
{   
parent = new int[size + 1];   
for (int i = 0; i <= size; i++) parent[i] = -1;   
}   
~MFSets() { delete []parent; }   
void merge(int root1, int root2)//root1!=root2   
{   
parent[root2] = root1;   
}   
int find(int n)   
{   
if (parent[n] < 0) return n;   
return find(parent[n]);   
}   
private:   
int size;   
int* parent;   
};   
#endif