|
|
Posted on 2009-04-10 19:41 lzmagic 阅读(4521) 评论(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吧
个人意见
|