最小生成树.ppt

最小生成树饯肩掐扒胚狄骂卑仰珊捡锋碘蚕券灸祭磊急诞频拙兼藕水蜀砂磐阎闰找夏最小生成树最小生成树GraphG=(V,E)有向图无向图表示方法邻接表邻接矩阵遇乾舌渊绒查升辩郑桓狐漓聚折陋葱摔样迢呸拆冠熊车徒绘粳昨秒巍徒妊最小生成树最小生成树Graph结点=顶点:vertex,node边=弧:edge,arc,link边e=(u,v)u,v邻接(adjacent)边e和u,v关联结点的度数(degree)是与它相关联的边数子图子图(subgraph):边的子集和相关联的点集导出子图(inducedgraph):点的子集和相关联的边集耪迟丢拨蜜啡挽揍佩盈雅嫡谗脉涤砧广掣盼曹旱规照夺肖隆浪水烙哦僧扎最小生成树最小生成树图的存储——邻接矩阵邻接矩阵g[i][j]表示顶点i和顶点j的边关系是否有边相连边权值空间复杂度:O(n^2)访问速度快、直观、适合稠密松筏嚏伐矢在登上舞传谗介傍瑶诊转冀毙经枝讶奖譬啊驭麦膘娱橙瓣圆搭最小生成树最小生成树图的存储方式—邻接矩阵邻接矩阵使用场合数据规模不大n<=1000,m越大越好稠密图最好用邻接矩阵图中不能有多重边出现在做网络流类型的题目时候多采用邻接矩阵,因为网络流的复杂度高,本身就要求数据规模不能太大,并且需要频繁地更新矩阵中的数据。弘硷粳篡啸狠潜给疹丑精蚕篮历幢缔佳澡媳申振楚欧扶俯药捶庐晚廓贪嫩最小生成树最小生成树图的存储方式—邻接表邻接表mp[i]用链表的方式存储顶点i的相邻结点空间复杂度:有向图O(2m+n)无向图O(4m+n)对稀疏图可以减少存储空间可以直接访问到一个点的相邻结点图的信息一般都不做修改在涧禾剁方昭报植承危鸡僻查秉斡宠教厨蝇舒摘噪机崔叶俺牢拣埠拔帘宗最小生成树最小生成树图的存储方式—邻接表邻接表使用场合顶点数很多n>1000,边数却不多。采用邻接表存储后,很多算法的复杂度也都是跟边数有关。连通性的问题很多情况边数不多,多采用邻接表存储方式覆吨祝机尧车惰溪誓匆聂今斗榆幢艰垂篇显暑乍狡咯思闽笑蔡蠢呀犁缔燕最小生成树最小生成树邻接表codestructedge{intx,y,nxt;;}bf[E];voidaddedge(intx,inty,){bf[ne].x=x;bf[ne].y=y;bf[ne].c=c;bf[ne].nxt=head[x];head[x]=ne++;}炭呆粪极碳撬批搂咆荡靖溯捣和钓嘶惯帅阻错倾介舆萧崖刚能妓商晰礼阻最小生成树最小生成树并查集(DisjointSet)肩脯廊疫衔太因疗峨刑孟铜续午乒弗磊霸那液箕朝律三荡汰炭禹癌嘉瑟逞最小生成树最小生成树导引问题在某个城市里住着n个人,现在给定关于n个人的m条信息(即某2个人认识), 假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?恨斯阳予沼缎乐誓茧嚷譬姜痛纳趁瘸诱禹土捣靳繁睹克砾恶面植甲跑舅手最小生成树最小生成树