|
|
Posted on 2009-04-10 19:41 lzmagic 閱讀(4572) 評論(1) 編輯 收藏 引用 所屬分類: Algorithm
  /**//**
 * KRUSKAL 最小生成樹算法 (Minimum Spanning Tree)
* 輸入：圖g； // 有向圖或者無向圖
* 輸出：(1)最小生成樹長sum；
* (2)最小生成樹mst。
* 結構: 圖g用頂點數n和邊集edges(優先隊列)表示，兩點是否連通用并查集實現。
* 算法：Kruskal算法
* 復雜度：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:兩個頂點 w:權
  Edge() { }
Edge(int u0, int v0, int w0):u(u0), v(v0), w(w0) { }
};
int n; // n : 頂點個數
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]) // 按個數求并(個數用負數表示)。
{
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();// 從未選邊集中尋找最小權的邊e。
root1 = ds.find(e.u), root2 = ds.find(e.v); // 獲取u、v所在的點集，
if (root1 != root2) // 如果u、v不是同一個點集，
{
sum += e.w; // 調整最小生成樹長
mst.push_back(e); // 把邊e放入最小生成樹mst中，
ds.unionSets(root1, root2); // 合并兩點所在的點集。
}
if (mst.size() == n - 1) return true; // 如果選取邊個數為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
# re: Kruskal算法 回復 更多評論
2010-12-06 22:14 by
這個程序是不是有個bug：
如果節點數量為1，邊數量為0
則應該是有生成樹的，但是kruskal函數返回結果為false吧
個人意見
|