这个帖子讲的很好
最小生成树
带权图分为有向和无向,无向图的最短路径又叫做最小生成树,有prime算法和kruskal算法;有向图的最短路径算法有dijkstra算法和floyd算法。
生成树的概念:联通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树 生成树是联通图的极小连通子图。所谓极小是指:若在树中任意增加一条边,则 将出现一个回路;若去掉一条边,将会使之编程非连通图。生成树各边的权 值总和称为生成素的权。权最小的生成树称为最小生成树,常用的算法有prime算法和kruskal算法。
最短路径问题旨在寻找图中两节点之间的最短路径,常用的算法有:floyd算法和dijkstra算法。
稠密图用prime, 稀疏图用kruskal
构造最小生成树
一般使用贪心策略,有prime算法和kruskal算法
Prime 算法 算法复杂度O(E + V log V) if you use a fibonacci heap
清空生成树,任取一个顶点加入生成树
在那些一个端点在生成树里,另一个端点不在生成树里的边中,选取一条权最小的边,将它和另一个端点加进生成树
重复步骤2,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树
int prime(int cur)
{
int index;
int sum = 0;
memset(visit, false, sizeof(visit));
visit[cur] = true;
for(int i = 0; i < m; i ++){
dist[i] = graph[cur][i];
}
for(int i = 1; i < m; i ++){
int mincost = INF;
for(int j = 0; j < m; j ++){
if(!visit[j] && dist[j] < mincost){
mincost = dist[j];
index = j;
}
}
visit[index] = true;
sum += mincost;
for(int j = 0; j < m; j ++){
if(!visit[j] && dist[j] > graph[index][j]){
dist[j] = graph[index][j];
}
}
}
return sum;
}
Kruskal算法
构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树的根节点,则它是一个含有n棵树的森林 。之后,从网的边集中选取一条权值最小的边,若该边的两个顶点分属不同的树 ,则将其加入子图,也就是这两个顶点分别所在的 两棵树合成一棵树;反之,若该边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林只有一棵树。kruskal算法能够在并查集的基础很快的实现。结合例子来介绍具体算法实现(其中并查集的部分可以详见并查集介绍部分)
核心在由权重从小到大取边, 利用并查集find root操作找出顶点不属于同一个树的边, 进行union操作
Prime 和KrusKal最大的不同是选边的时候,prime 选的边总是维护一个连接的components,而总是选择最小的每次连接两个不同components的边.
复杂度:max(O(ElogE) , O(ElogV))
//合并x,y所在的两个集合:利用Find_Set找到其中两个
//集合的祖先,将一个集合的祖先指向另一个集合的祖先。
void Union(int x, int y)
{
x = find_set(x);
y = find_set(y);
if(x == y){
return ;
}
if(rank[x] < rank[y]){
father[x] = find_set(y);
}
else{
if(rank[x] == rank[y]){
rank[x] ++;
}
father[y] = find_set(x);
}
return ;
}
bool cmp(pnode a, pnode b)
{
return a.val < b.val;
}
int kruskal(int n) //n为边的数量
{
int sum = 0;
make_set();
for(int i = 0; i < n; i ++){ //从权最小的边开始加进图中
if(find_set(edge[i].start) != find_set(edge[i].end)){
Union(edge[i].start, edge[i].end);
sum += edge[i].val;
}
}
return sum;
}
http://www.lintcode.com/en/problem/minimum-spanning-tree/
Minimum Spanning Tree
给十几个城市供电,连接不同城市的花费不同,让花费最小同时连到所有的边。给出一系列connection类,里面是edge两端的城市名和它们之间的一个cost,找出要你挑一些边,把所有城市连接起来并且总花费最小。不能有环,最后所以城市要连成一个连通块。
不能的话输出空表,最后还要按城市名字排序输出,按照node1来排序,如果一样的话再排node2。