MST-最小生成树ppt课件

MinimumSpanningTree,1,FlightPathProblem,2,FlightPathProblem,Considerthegraphrepresentingtheairlineconnectionsbetweensevencities.,a,b,c,d,e,f,g,6,5,9,16,13,12,15,8,3,7,theleastflightpaths,theleastcost,FlightPathProblem,MinimumSpanningTree,3,MinimumSpanningTree,IntroductionProblemDefinitionBoruvkasalgorithmConclusion,4,Introduction,Theminimumspanningtreeproblemisoneoftheoldestandmostbasicgraphproblemsintheoreticalcomputerscience.ItshistorydatesbacktoBoruvkasalgorithmin1926andtilltodayitisaextensivelyresearchedproblemwithnewbreakthroughsonlyrecently.,5,ProblemDefinition,Allthegraphsinthisreportarefinite,simple,andundirected.Wedenotebynthenumberofvertices,mthenumberofedgesinagraphG=(V,E).Ourgraphsareweighted,w(e)denotingthedistinctweightoftheedgee.,6,ProblemDefinition,AspanningtreeinGisanacyclicsubgraphofGthatincludeseveryvertexofGandisconnected;everyspanningtreehasexactlyn-1edges.Theweightofatreeisdefinedtobethesumoftheweightsofitsedges.Aminimumspanningtree(MST)isaspanningtreeofminimumweight.,7,MSTP:,TheMinimalSpanningTreeproblem(MSTP)is:Input:AweightedgraphG=(v,e,w).Output:TheUniquespanningtreeTthatminimizes.,8,MSF,WhentheinputgraphGisnotconnected,aspanningtreedoesnotexistandwegeneralizethenotionofaminimumspanningtreetothatofaminimumspanningforest(MSF).AspanningforestisaforestwhosetreesarespanningtreesfortheconnectedcomponentsofthegraphG.,9,MSF,SowhenGisnotconnectedwefindtheminimalspanningforestMSF:Asetoftrees,oneineachoftheconnectedcomponentofG,eachtreebeingaminimalspanningtreeofthegraphinducedbythecomponent.Aspanningforestisaspanningtreeifandonlyifthegraphisconnected.,10,MST,aspanningtree:ahbcigfedtheweightsofthistree:8+11+8+2+6+2+10+9=56.minimalspanningtree:abcifghdetheweightsofMST:4+8+7+2+4+9+2+1=3756.,11,MST,Givenanedge-weightedgraph,thisproblemcallsforfindingasubtreespanningallthevertices,whosetotalweightisminimal.Foran-degreecompletegraph,therearespanningtrees.Thenthecentralopenquestionis:Doesthereexistalineartimedeterministicalgorithmthatfindstheminimalspanningtree?,12,MSTP,TheMSTPisoneofthebest-studiedproblemsincombinatorialoptimization.Avarietyofalgorithmshavebeendevelopedforthisproblem,mostofwhicharebasedonagreedystrategyandruninnear-linearO(mlogn)time,e.g.,Boruvkasalgorithm,Kruskalsalgorithm,Primsalgorithm.,13,Boruvkasalgorithm,ThefirstMSTalgorithmwasdevisedbyBoruvka,thealgorithmisbasedonthegreedystrategy.ThebasicstepinBoruvkasalgorithmistheheartofmanyMSTalgorithmstilltoday.,14,Boruvkasalgorithm,westartwithone-vertextrees;foreachvertexv,welookforanedge(vw)ofminimumweightamongalledgesoutgoingfromvcreatesmalltreesbyincludingtheseedges.Then,welookforedgesofminimalweightthatcanconnecttheresultingtreetolargertrees.Theprocessisfinishedwhenonetreeiscreated.,15,TheprocessofBoruvkasalgorithm,a,b,c,d,e,f,g,a,b,c,d,e,f,g,a,b,c,d,e,f,g,6,5,9,16,13,12,15,8,3,7,5,6,7,8,3,12,2.Forthisgraph,outofsevenone-vertex,twotreesarecreatedbecause,forverticesaandc,edge(ac)ischosen,forvertexb,edge(ab)ischosen,forvertexd,edge(df)ischosen,forvertexe,edge(eg)ischosen,andforverticesfandg,edge(fg)ischosen.,3.forthetree(abc)andthetree(defg),edge(cf)isselected,sinceitistheshortestedgethatconnectsthesetwotrees,resultinginonespanningtree.,3,8,7,5,6,16,pseudocode:,BoruvkaAlgorithnm(weightedconnectedundirectedgraph)makeeachvertextherootofaone-nodetree;WhilethereismorethanonetreeForeachtreete=minimumweightedge(vu)wherevisincludedintanduisnot;createatreebycombiningtandthetreethatincludesuifsuchatreedoesnotexistyet;,17,Boruvkasalgorithm,Doesthisalgorithmruninalineartime?BoruvkasalgorithmthusreducestheMSTprobleminann-vertexgraphwithmedgestotheMSTprobleminan(n/2)-vertexgraphwithatmostmedges.ThetimerequiredforthereductionisonlyO(m+n).Itfollowsthattheworst