• / 46
  • 下载费用:10 金币  

最小生成树.ppt

关 键 词:
最小生成树.ppt
资源描述:
最小生成树,,Graph,G = (V, E) 有向图 无向图 表示方法 邻接表 邻接矩阵,Graph,结点 = 顶点 : vertex, node 边 = 弧 : edge, arc, link 边e = (u, v) u , v 邻接 (adjacent) 边 e 和 u, v 关联 结点的度数(degree)是与它相关联的边数 子图 子图(subgraph) : 边的子集和相关联的点集 导出子图(induced graph) : 点的子集和相关联的边集,图的存储——邻接矩阵,邻接矩阵 g[i][j] 表示顶点i和顶点j的边关系 是否有边相连 边权值 空间复杂度:O(n^2) 访问速度快、直观、适合稠密,图的存储方式—邻接矩阵,邻接矩阵使用场合 数据规模不大n = 1000,m越大越好 稠密图最好用邻接矩阵 图中不能有多重边出现 在做网络流类型的题目时候多采用邻接矩阵,因为网络流的复杂度高,本身就要求数据规模不能太大,并且需要频繁地更新矩阵中的数据。,图的存储方式—邻接表,邻接表 mp[i]用链表的方式存储顶点i的相邻结点 空间复杂度:有向图O(2m+n)无向图O(4m+n) 对稀疏图可以减少存储空间 可以直接访问到一个点的相邻结点 图的信息一般都不做修改,图的存储方式—邻接表,邻接表使用场合 顶点数很多n1000,边数却不多。 采用邻接表存储后,很多算法的复杂度也都是跟边数有关。 连通性的问题很多情况边数不多,多采用邻接表存储方式,邻接表code,struct edge { int x, y, nxt; typec c; } bf[E];void addedge(int x, int y, typec c) {bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;bf[ne].nxt = head[x]; head[x] = ne++; },并查集 (Disjoint Set),,导引问题,在某个城市里住着n个人,现在给定关于 n个人的m条信息(即某2个人认识),假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?,如何实现?,,什么是并查集?,英文:Disjoint Set,即“不相交集合” 将编号分别为1…N的N个对象划分为不相交集合, 在每个集合中,选择其中某个元素代表所在集合。常见两种操作: 合并两个集合 查找某元素属于哪个集合,所以,也称为“并查集”,实现方法(1),用编号最小的元素标记所在集合; 定义一个数组 set[1n] ,其中set[i] 表示元素i 所在的集合;,i,Set(i),不相交集合: {1,3,7}, {4}, {2,5,9,10}, {6,8},方法(1)——效率分析,find1(x) {return set[x]; },Merge1(a,b) { i = min(a,b);j = max(a,b);for (k=1; k=N; k++) {if (set[k] == j)set[k] = i;} },Θ(1),Θ(N),有待改进?,对于“合并操作”,必须搜索全部元素!,树结构如何?,实现方法(2),每个集合用一棵“有根树”表示 定义数组 set[1n] set[i] = i , 则i表示本集合,并是集合对应树的根 set[i] = j, ji, 则 j 是 i 的父节点.,方法(2)——效率分析,find2(x) {r = x;while (set[r] != r)r = set[r];return r; },merge2(a, b) {if (ab)set[b] = a;elseset[a] = b; },Θ(1),最坏情况Θ(N) 一般情况是…?,困惑~~~,性能有本质改进?,如何避免最坏情况?,避免最坏情况,方法:将深度小的树合并到深度大的树 实现:假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是: max(h1,h2), if h1h2. h1+1, if h1=h2. 效果:任意顺序的合并操作以后,包含k个节点的树的最大高度不超过,优化后算法及效率,merge3(a,b) { if (height(a) == height(b)) {height(a) = height(a) + 1;set[b] = a; } else if (height(a) height(b))set[a] = b;else set[b] = a; },find2(x) {r = x;while (set[r] != r)r = set[r];return r; },最坏情况Θ(log N),Θ(1),进一步优化——路径压缩,思想:每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快 步骤: 第一步,找到根结点 第二步,修改查找路径
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:最小生成树.ppt
链接地址:https://www.weizhuannet.com/p-9861314.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开