锐客网

  1. 首页 > 睿知 > it技术 > >

最小生成树（贪心思想）

最小生成树是一个连通加权无向图中一棵权值最小的生成树。
Prim算法思想：
设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一棵MST（Minimum Spanning Tree，最小生成树）。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
代码实现：

//最小生成树 int map[N][N]; //存i到j的路径 int vis[N]; //存该节点是否已经选取过了 int dist[N]; //树到其它各个节点的距离int prim() { int sum =0; for(int i=0; imap[index][j]) dist[j]=map[index][j]; } } return sum; }

时间复杂度：O(n^2)
Kruskal算法思想：
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，需要使用并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。
基本思想是以边为主导地位，始终都是选择当前可用的最小权值的边，步骤如下：
  1. 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T（V,?），图中每个顶点自成一个连通分量
  2. 将原图中的所有边按权值从小到大排序
  3. 从权值最小的边开始，如果这条边连接的两个顶点于图T中不在同一个连通分量中，则添加这条边到图T中
  4. 重复3，直至T中所有顶点在同一个连通分量中为止
    代码实现：
#include #include #include using namespace std; #define maxn 110; //最多点个数 int fa[110]; //并查集存根节点 int n, m; //顶点个数， 边数struct Edge{ int x, y; int val; }edge[5000]; bool cmp(Edge a, Edge b) { return a.val < b.val; }int findfa(int x)//寻找所在树的根节点，判断是否在同一个连同分量的依据 { if(fa[x] != x) fa[x] = findfa(fa[x]); return fa[x]; //return fa[x] == x ? x : (fa[x] = findfa(fa[x])); }int Union(int x, int y)//并查集合并两棵树 { fa[findfa(x)] = findfa(y); }int Kruskal() { int cnt = 0; long sum = 0; for(int i=1; i<=n; i++)//顶点的编号为[1..n] fa[i] = i; sort(edge, edge+m, cmp); //把边从小到大排序，m为边的数目for(int i=0; i= n-1) break; //n-1条边均加入同一个集合中 } } return sum; }int main() { cin>>n>>m; for(int i=0; i>edge[i].x>>edge[i].y>>edge[i].val; cout<

时间复杂度： O(E*logE)
Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(ElogE)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环E次，所以这一步的时间复杂度为O(Eα(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(ElogE)。
【最小生成树（贪心思想）】总结：
Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：
  • 对于Prim, 其选取的边（u,v）必有一个顶点已经被覆盖，另一个顶点未被覆盖，适用于稠密图。
  • 对于Kruskal, 其选取的边（u,v）任意，只要这个边的加入不会使被覆盖的顶点构成回路，适用于稀疏图。

    推荐阅读


    上一篇：2019-10-07

    下一篇：第六章.青梅煮酒（4）