最小生成树.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个人认识), 假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?还稽雏尖幻银臂烹碑软篆础终虫岿雕赠寞读矾留螟软砍钾镰嘱帛逗耙易悸最小生成树最小生成树