|
|
Posted on 2009-04-10 19:41 lzmagic 閱讀(4565) 評論(1) 編輯 收藏 引用 所屬分類: Algorithm
  /**//**
 * KRUSKAL 最小生成樹算法 (Minimum Spanning Tree)
* 輸入：圖g； // 有向圖或者無向圖
* 輸出：(1)最小生成樹長sum；
* (2)最小生成樹mst。
* 結(jié)構(gòu): 圖g用頂點(diǎn)數(shù)n和邊集edges(優(yōu)先隊(duì)列)表示，兩點(diǎn)是否連通用并查集實(shí)現(xiàn)。
* 算法：Kruskal算法
* 復(fù)雜度：O(|E|*log|E|)~O(|E|*log|V|)
 */
 #include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
struct Edge
 {
int u, v, w; // u、v:兩個(gè)頂點(diǎn) w:權(quán)
  Edge() { }
Edge(int u0, int v0, int w0):u(u0), v(v0), w(w0) { }
};
int n; // n : 頂點(diǎn)個(gè)數(shù)
vector<Edge> edges; // edges : 圖g的所有邊
int sum; // sum : 最小生成樹長
vector<Edge> mst; // mst : 最小生成樹(用邊集表示)
class DisjSets
{
vector<int> s;
public:
DisjSets(int n) : s(n, -1) { };
int find (int x)
{
if (s[x] < 0) return x;
else return s[x] = find(s[x]); // 壓縮路徑。
 };
void unionSets(int root1, int root2)
{
if (s[root1] > s[root2]) // 按個(gè)數(shù)求并(個(gè)數(shù)用負(fù)數(shù)表示)。
{
s[root2] += s[root1];
s[root1] = root2;
}
else
{
s[root1] += s[root2];
s[root2] = root1;
}
};
};
bool Cmp(const Edge &lhs, const Edge &rhs)
{
return lhs.w > rhs.w;
}
bool Kruskal()
{
DisjSets ds(n);
make_heap(edges.begin(), edges.end(), Cmp); // 對邊集建堆。
int root1, root2;
Edge e;
while (!edges.empty()) // 遍歷所有邊，
{
e = edges.front(); pop_heap(edges.begin(), edges.end(), Cmp); edges.pop_back();// 從未選邊集中尋找最小權(quán)的邊e。
root1 = ds.find(e.u), root2 = ds.find(e.v); // 獲取u、v所在的點(diǎn)集，
if (root1 != root2) // 如果u、v不是同一個(gè)點(diǎn)集，
{
sum += e.w; // 調(diào)整最小生成樹長
mst.push_back(e); // 把邊e放入最小生成樹mst中，
ds.unionSets(root1, root2); // 合并兩點(diǎn)所在的點(diǎn)集。
}
if (mst.size() == n - 1) return true; // 如果選取邊個(gè)數(shù)為n - 1，成功。
}
return false;
}
int main()
{
n = 7;
edges.clear();
edges.push_back(Edge(0, 1, 2)); edges.push_back(Edge(0, 2, 4)); edges.push_back(Edge(0, 3, 1));
edges.push_back(Edge(1, 3, 3)); edges.push_back(Edge(1, 4, 10));
edges.push_back(Edge(2, 3, 2)); edges.push_back(Edge(2, 5, 5));
edges.push_back(Edge(3, 4, 7)); edges.push_back(Edge(3, 5, 8)); edges.push_back(Edge(3, 6, 4));
edges.push_back(Edge(4, 6, 6));
edges.push_back(Edge(5, 6, 1));
sum = 0;
mst.clear();
if(Kruskal())
{
cout << sum << endl;
for (vector<Edge>::iterator it = mst.begin(); it != mst.end(); ++it)
cout << it->u << "->" << it->v << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}
system("pause");
return 0;
}
Feedback
這個(gè)程序是不是有個(gè)bug：
如果節(jié)點(diǎn)數(shù)量為1，邊數(shù)量為0
則應(yīng)該是有生成樹的，但是kruskal函數(shù)返回結(jié)果為false吧
個(gè)人意見
|