[最小生成树.ppt

最小生成树 并查集（Disjoint Set） 导引问题 在某个城市里住着n个人，现在给定关于 n个人的m条信息（即某2个人认识）， 假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？ 如何实现？ 什么是并查集？ 英文：Disjoint Set，即“不相交集合” 将编号分别为1…N的N个对象划分为不相交集合， 在每个集合中，选择其中某个元素代表所在集合。 常见两种操作： 合并两个集合 查找某元素属于哪个集合 实现方法（1） 用编号最小的元素标记所在集合； 定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合； 方法(1)——效率分析 有待改进？ 对于“合并操作”，必须有哪些信誉好的足球投注网站全部元素！ 实现方法（2） 每个集合用一棵“有根树”表示 定义数组 set[1..n] set[i] = i , 则i表示本集合，并是集合对应树的根 set[i] = j, ji, 则 j 是 i 的父节点. 方法(2)——效率分析 困惑~~~ 性能有本质改进? 避免最坏情况 方法：将深度小的树合并到深度大的树 实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是: max(h1,h2), if h1h2. h1+1, if h1=h2. 效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过 优化后算法及效率 进一步优化——路径压缩 思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快 步骤: 第一步，找到根结点 第二步，修改查找路径上的所有节点，将它们都指向根结点 带路径压缩的查找算法 find3(x) { r = x; while (set[r] r) //循环结束，则找到根节点 r = set[r]; i = x; while (i r) //本循环修改查找路径中所有节点 { j = set[i]; set[i] = r; i = j; }} 路径压缩示意图 示例—畅通工程(HDOJ-1232) 题目描述： 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 题目分析 最赤裸裸的并查集，无话可说～ 附:参考源码(HDOJ-1232) #include stdio.h int bin[1002]; int findx(int x) { int r=x; while(bin[r] !=r) r=bin[r]; return r; } void merge(int x,int y) { int fx,fy; fx = findx(x); fy = findx(y); if(fx != fy) bin[fx] = fy; } 示例—小希的迷宫(HDOJ-1272) 题目链接 下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 题目分析: 该你们来说了～ 经典应用——最小生成树 1、什么是——生成树？ 经典应用——最小生成树 2、什么是——最小生成树？ MST性质（prim算法原理） G=(V，E)是一个网络，U是顶点集合V的一个真子集。 如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边， 则一定存在G的一棵最小生成树包括此边(u,v)。 MST必包含连通图中任意两个顶点划分之间的最小权的边。 （任意割集中的最小边） 经典应用——最小生成树 3、如何求——最小生成树？ //无向图最小生成树,prim算法,邻接阵形式,复杂度O(n^2) //返回最小生成树的长度,传入图的大小n和邻接阵mat,不相邻点边权inf //可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1 //必须保证图的连通的! #define MAXN 200 #define inf 1000000000 typedef double elem_t; elem_t prim(int n,elem_t mat[][MAXN],int* pre){ elem_t min[MAXN],ret=0; int v[MAXN],i,j,k; for (i=0;in;i++) min[i]=inf,v[i]=0,pre[i]=-1; for (min[j