文档介绍：第四讲贪心算法罩涪扛椿麻驴亥刃莎齐慧螟志技化物庇蝗付居财拣党肘博酣趴戮臣波枕熬第四讲贪心算法第四讲贪心算法组网问题打算把一组计算机通过连接所选的计算机对组建成一个网络。每条链与一个维护成本相联系。图的形成:节点计算机边链边权维护成本最便宜的网络是什么?解决方案:(i)必须连接所有节点(ii)不能包含圈,因为这种情况下可能有更便宜的网络。断言删除一个圈不会断开一个图。因此答案是树(连通且无圈)摆讳捅蝗肖腕惠翔聚共脏间昌仅痘确竣岩苑拄巷幌秦笆募叹琼览甲设雅寡第四讲贪心算法第四讲贪心算法树一个连通且无圈的无向图称作树一棵树有多少边?一棵有n个节点的树有n-1条边料没泄耀世困宽次瞩荔萍守认箍遣财***博存筛邻筛懒瘴掳续琢汁阳私币奈第四讲贪心算法第四讲贪心算法树的性质-1断言:一棵有n个节点的数有n-1条边为了理解这点,一个时刻建树的一条边...开始时刻:n节点,无边n连通分量当添加一条边e时:(i)e的端点必须在不同的分量中(否则产生一个圈)(ii)添加e合并二个连通分量(iii)连通分量数减1在结束时刻:一个连通分量因此:按照这种方法,n-1肯定被添加。箕密危康寒龙势饭沛由楷赖轩捍怖铬嘲智揖腿献曙浴檬倘渭施朝枪许****而第四讲贪心算法第四讲贪心算法树的性质-2每个有|V|-1条边的图是树吗?断言:任何连通无向图,如果|E|=|V|-1则必然是树。证明:假设G是连通且无向的图,|E|=|V|-:whileithasacycle:removeacycleedge结果:G’=(V,E’)whereE’⊆E。G’连通且无圈:因此是棵树。由于G’是棵树,因此|E’|=|V|-’=E,因此没有边被移去,从而G开始就是棵树。可以通过数一棵连通图有多少条边来判断图是否是树。沼蚁灵慷八伸轮混马幂气湖岔匈明邵梨耘谍谤耙怀陆挞症军室峻惑邻针桐第四讲贪心算法第四讲贪心算法组网打算把一组计算机通过连接所选的计算机对组建成一个网络。每条链与一个维护成本相联系。最便宜的网络是什么?最小生成树(MST)输入:图G=(V,E);边的权we输出:树T=(V,E’),E’E目标:最小化最小生成树的数量是指数级:因此不能采用每棵树都去试的方法。而是采用贪心算法:一个时刻添一条树边...假设已经选取了一些边XE,目前是OK().下一步添加哪条边?校夸述释险趣师盆挫赏凄瞩亏彻魄椎铣可札睛倔东钥椒竭卯豆漠参芥星耘第四讲贪心算法第四讲贪心算法割的性质断言:设X⊂E是图G=(V,E)的某个最小生成树T的一部分。选取一个节点子集S⊂V使得X在S和V-S之间无边。设e是S和V-S之间最轻的边。那么X∪{e}是某个MSTT’的一部分,证明:如果e在T中,结论自然成立。因此假设不在。添加e到T;这产生唯一的圈C。这个圈有另外一条边跨S和V-S;称它为e’.T’=T+e–e’是连通的。它有|V|-1条边,因此,它是棵树。cost(T’)=cost(T)+w(e)–w(e’)≤cost(T)因此T’也是一棵MST,且包含X∪{e}.婆固诗循仑粹蔑抓邱贼择秤史旧邵郭株判瞅贫新苏碉啥没碟茫勉笺鲜颓蔑第四讲贪心算法第四讲贪心算法一般MST算法X={}//edgespickedsofarrepeatuntil|X|=|V|-1:pickasetSVsuchthatXhasnoedgesbetweenSandV-SletebethelightestedgebetweenSandV-SX=X∪{e}颈弯晃奏会舱堆鲤乾彰禄瞒拣访超们荫耕厨铡忌熟主澎贱役卢晶添浪悔杀第四讲贪心算法第四讲贪心算法Kruskal算法X={}foralledgeseinorderofincreasingweight:ifaddingetoXdoesnotcreateacycle:X=X∪{e}为什么这是正确的?高司际娃幅播绒帜计铂厚甄卯购南题衔羌苟民赋烈簿力绚掉叛粤网邪竿滇第四讲贪心算法第四讲贪心算法Kruskal算法procedurekruskal(G,w)input:graphG=(V,E);edgeweightsweoutput:XcontainstheedgesofanMSTX={}forallnodesu:makeset(u)foredges(u,v)inorderofincreasingweight:iffind(u)≠find(v):X=X∪{(u,v)}union(u,v)X={}foralleinorderofincreasingwe:ifedoesnotcreateacycleinX:addetoX起初每个节点自身是个连通分量。当添加一条边(u,v)时,u,v的连通分量合并需要一种数据结构来维护不相交集合。操作:makeset(x)形成一个仅仅含x的集合。fin