國外算法設(shè)計與分析課件2

GreedyAlgorithms(I)Greed,forlackofabetterword,isgood!Greedisright!Greedworks!-MichaelDouglas,U.S.actorintheroleofGordonGecko,inthefilmWallStreet,1987GreedyAlgorithms(I)Greed,foMaintopicsIdeaofthegreedyapproachChange-makingproblemMinimumspanningtreeproblemPrim’salgorithmKruskal’salgorithmPropertiesofminimumspanningtree(additivepart)Bottleneckspanningtree(additivepart)MaintopicsIdeaofthegreedyExpectedOutcomesStudentshouldbeabletosummarizetheideaofthegreedytechniquelistseveralapplicationsofthegreedytechniqueapplythegreedytechniquetochange-makingproblemdefinetheminimumspanningtreeproblemdescribeideasofPrimandKruskal’salgorithmsforcomputingminimumspanningtreeprovethecorrectnessofthetwoalgorithmsanalyzethetimecomplexitiesofthetwoalgorithmsunderdifferentdatastructuresprovethevariouspropertiesofminimumspanningtreeExpectedOutcomesStudentshoulGlossaryGreedy:貪婪的Change-makingproblem:找零錢問題Cashier:收銀員Denomination:貨幣單位，面額Quarter,dime,nickel,penny:2角5分，1角，5分，1分（美國硬幣單位）Irrevocable：不可取消的，不可逆的Spanningtree:生成樹，支撐樹GlossaryGreedy:貪婪的AnticipatorySet:

ChangeMakingProblemHowtomake48centsofchangeusingcoinsofdenominationsof25(1quartercoin),10(1dimecoin),5(1nickelcoin),and1(1pennycoin)sothatthetotalnumberofcoinsisthesmallest?Theidea:Takethecoinwithlargestdenominationwithoutexceedingtheremainingamountofcents,makethelocallybestchoiceateachstep.Isthesolutionoptimal?Yes,theproofisleftasexercise.AnticipatorySet:

ChangeMakiGeneralChange-MakingProblemGivenunlimitedamountsofcoinsofdenominationsd1>…>dm,givechangeforamountnwiththeleastnumberofcoins.Doesthegreedyalgorithmalwaysgiveanoptimalsolutionforthegeneralchange-makingproblem?Wegivethefollowingexample,Example:d1=7c,d2=5c,d3=1c,andn=10c,notalwaysproducesanoptimalsolution.infact,forsomeinstances,theproblemmaynothaveasolutionatall!considerinstanced1=7c,d2=5c,d3=3c,andn=11c.But,thisproblemcanbesolvedbydynamicprogramming,pleasetrytodesignanalgorithmforthegeneralchange-makingproblemafterclass.GeneralChange-MakingProblemGGreedyAlgorithmsAgreedyalgorithmmakesalocallyoptimalchoicestepbystepinthehopethatthischoicewillleadtoagloballyoptimalsolution.

Thechoicemadeateachstepmustbe:FeasibleSatisfytheproblem’sconstraintslocallyoptimalBethebestlocalchoiceamongallfeasiblechoicesIrrevocableOncemade,thechoicecan’tbechangedonsubsequentsteps.Dogreedyalgorithmsalwaysyieldoptimalsolutions?Example:changemakingproblemwithadenominationsetof7,5and1,andn=10?GreedyAlgorithmsAgreedyalgoApplicationsoftheGreedyStrategyOptimalsolutions:someinstancesofchangemakingMinimumSpanningTree(MST)Single-sourceshortestpathsHuffmancodesApproximations:TravelingSalesmanProblem(TSP)KnapsackproblemotheroptimizationproblemsForsomeproblems,yieldsanoptimalsolutionforeveryinstance.Formost,doesnotbutcanbeusefulforfastapproximations.ApplicationsoftheGreedyStrMinimumSpanningTree(MST)SpanningtreeofaconnectedgraphGisaconnectedacyclicsubgraph(tree)ofGthatincludesallofG’svertices.Note:aspanningtreewithnverticeshasexactlyn-1edges.MinimumSpanningTreeofaweighted,connectedgraphGisaspanningtreeofGofminimumtotalweight.Example:MinimumSpanningTree(MST)SpaMSTProblemGivenaconnected,undirected,weightedgraphG=(V,E),findaminimumspanningtreeforit.ComputeMSTthroughBruteForce?Kruskal:1956,Prim:1957BruteforceGenerateallpossiblespanningtreesforthegivengraph.Findtheonewithminimumtotalweight.FeasibilityofBruteforcePossibletoomanytrees(exponentialfordensegraphs)MSTProblemGivenaconnected,ThePrim’sAlgorithmIdeaofthePrim’salgorithmPseudo-codeofthealgorithmCorrectnessofthealgorithm(important)TimecomplexityofthealgorithmThePrim’sAlgorithmIdeaofthIdeaofPrimGrowasingletreebyrepeatedlyaddingtheleastcostedge(greedystep)thatconnectsavertexintheexistingtreetoavertexnotintheexistingtreeIntermediatesolutionisalwaysasubtreeofsomeminimumspanningtree.IdeaofPrimGrowasingletreePrim’sMSTalgorithmStartwithatree,T0,consistingofonevertex“Grow”treeonevertex/edgeatatimeConstructaseriesofexpandingsubtreesT1,T2,…Tn-1..AteachstageconstructTifromTi-1byaddingtheminimumweightedgethatconnectingavertexintree(Ti-1)toavertexnotyetinthetreethisisthe“greedy”step!AlgorithmstopswhenallverticesareincludedPrim’sMSTalgorithmStartwithPseudocodeofthePrimALGORITHMPrim(G)//Prim’salgorithmforconstructingaminimumspanningtree//Input:AweightedconnectedgraphG=(V,E)//Output:ET,thesetofedgescomposingaminimumspanningtreeofGVT{v0}//v0canbearbitrarilyselectedETfor

i1to|V|-1dofindaminimum-weightedgee*=(v*,u*)amongalltheedges(v,u)suchthatvisinVTanduisinV-VT

VTVT{u*}

ETET{e*}return

ETPseudocodeofthePrimALGORITHAnexampleaedcb1524637Anexampleaedcb1524637ThePrim’salgorithmisgreedy!Thechoiceofedgesaddedtocurrentsubtreesatisfyingthethreepropertiesofgreedyalgorithms.Feasible,eachedgeaddedtothetreedoesnotresultinacycle,guaranteethatthefinalETisaspanningtreeLocaloptimal,eachedgeselectedtothetreeisalwaystheonewithminimumweightamongalltheedgescrossingVTandV-VTIrrevocable,onceanedgeisaddedtothetree,itisnotremovedinsubsequentsteps.ThePrim’salgorithmisgreedyCorrectnessofPrimProvebyinductionthatthisconstructionprocessactuallyyieldsMST.T0isasubsetofallMSTsSupposethatTi-1isasubsetofsomeMSTT,weshouldprovethatTiwhichisgeneratedfromTi-1isalsoasubsetofsomeMST.Bycontradiction,assumethatTidoesnotbelongtoanyMST.Letei=(u,v)betheminimumweightedgefromavertexinTi-1toavertexnotinTi-1usedbyPrim’salgorithmtoexpandingTi-1toTi,accordingtoourassumption,eicannotbelongtoMSTT.AddingeitoTresultsinacyclecontaininganotheredgee’=(u’,v’)connectingavertexu’inTi-1toavertexv’notinit,andw(e’)w(ei)accordingtothegreedyPrim’salgorithm.Removinge’fromTandaddingeitoTresultsinanotherspanningtreeT’withweightw(T’)w(T),indicatingthatT’isaminimumspanningtreeincludingTiwhichcontradicttoassumptionthatTidoesnotbelongtoanyMST.CorrectnessofPrimProvebyinCorrectnessofPrimCorrectnessofPrimImplementationofPrimHowtoimplementthestepsinthePrim’salgorithm?Firstidea,labeleachvertexwitheither0or1,1representsthevertexinVT,and0otherwise.Traversetheedgesettofindanminimumweightedgewhoseendpointshavedifferentlabels.Timecomplexity:O(VE)ifadjacencylinkedlistandO(V3)foradjacencymatrixForsparsegraphs,useadjacencylinkedlistAnyimprovement?ImplementationofPrimHowtoiNotationsT:theexpandingsubtree.Q:theremainingvertices.Ateachstage,thekeypointofexpandingthecurrentsubtreeTistoDeterminewhichvertexinQisthenearestvertextoT.Qcanbethoughtofasapriorityqueue:Thekey(priority)ofeachvertex,key[v],meanstheminimumweightedgefromvtoavertexinT.Key[v]is∞ifvisnotlinkedtoanyvertexinT.Themajoroperationistotofindanddeletethenearestvertex(v,forwhichkey[v]isthesmallestamongallthevertices)RemovethenearestvertexvfromQandadditandthecorrespondingedgetoT.Withtheoccurrenceofthataction,thekeyofv’sneighborswillbechanged.ToremembertheedgesoftheMST,anarray[]isintroducedtorecordtheparentofeachvertex.Thatis[v]isthevertexintheexpandingsubtreeTthatisclosesttovnotinT.NotationsT:theexpandingsubtAdvancedPrim’sAlgorithmALGORITHMMST-PRIM(G,w,r)//w:weight;r:root,thestartingvertexforeachu

V[G]

do

key[u]

[u]NIL

//[u]:theparentofukey[r]0QV[G] //Nowthepriorityqueue,Q,hasbeenbuilt.while

Q

douExtract-Min(Q)//removethenearestvertexfromQ

foreachvAdj[u]//updatethekeyforeachofv’sadjacentnodes.

do

if

vQandw(u,v)<key[v]

then

[v]ukey[v]w(u,v)AdvancedPrim’sAlgorithmALGO國外算法設(shè)計與分析課件2TimeComplexityofPrim’salgorithmNeedpriorityqueueforlocatingthenearestvertexUseunorderedarraytostorethepriorityqueue: Efficiency:Θ(n2)Usebinarymin-heaptostorethepriorityqueue Efficiency:Forgraphwithnverticesandmedges:

O(mlogn)UseFibonacci-heaptostorethepriorityqueue:Efficiency:Forgraphwithnverticesandmedges:

O(nlogn+m)TimeComplexityofPrim’salgoKruskal’sMSTAlgorithmEdgesareinitiallysortedbyincreasingweightStartwithanemptyforestF0“grow”MSToneedgeatatimethroughaseriesofexpandingforestsF1,F2,…,Fn-1intermediatestagesusuallyhaveforestoftrees(notconnected)ateachstageaddminimumweightedgeamongthosenotyetusedthatdoesnotcreateacycleneedefficientwayofdetecting/avoidingcyclesalgorithmstopswhenallverticesareincludedKruskal’sMSTAlgorithmEdgesaCorrectnessofKruskalSimilartotheproofofPrimProvebyinductionontheconstructionprocessactuallygenerateaMSTConsiderF0,F1,…,Fn-1CorrectnessofKruskalSimilarBasicKruskal’sAlgorithmALGORITHMKruscal(G)//Input:AweightedconnectedgraphG=<V,E>

//Output:ET,thesetofedgescomposingaminimumspanningtreeofG.SortEinnondecreasingorderoftheedgeweightsw(ei1)<=…<=w(ei|E|) ET

;ecounter

0

//initializethesetoftreeedgesanditssizek0

whileencounter<|V|-1

do kk+1

ifET

U{eik}isacyclic

ET

ETU{eik};ecounterecounter+1returnETBasicKruskal’sAlgorithmALGORKruskal’sAlgorithm(AdvancedPart)Kruskal’sAlgorithm(Advanced國外算法設(shè)計與分析課件2Kruskal:TimeComplexity

O(EV)whendisjoint-setdatastructurearenotused.Whenusedisjoint-setdatastructurewithunion-by-rankandpath-compressionheuristics:InitializingthesetAinline1takesO(1)time.

O(V)MAKE-SEToperationsinlines2-3Sorttheedgesinline4takesO(ElogE)time.Theforloopoflines5-8performsO(E)FIND-SETandUNIONoperationsonthedisjoint-setforestb)andd)takeatotalofO((V+E)(V))Line9:O(V+E)Notethat:E

V-1and(V)=O(logV)=O(logE)andEV2SOtotaltimeis:O(ElogV)Kruskal:TimeComplexityO(EV)PropertiesofMSTProperty1:Let(u,v)beaminimum-weightedgeinagraphG=(V,E),then(u,v)belongstosomeminimumspanningtreeofG.Proofhint:suppose(u,v)isnotinMSTT,constructanotherMSTT’including(u,v).PropertiesofMSTProperty1:PropertiesofMSTProperty2Agraphhasauniqueminimumspanningtreeifalltheedgeweightsarepairwisedistinct.Theconversedoesnothold.PropertiesofMSTProperty2PropertiesofMSTProperty3LetTbeaminimumspanningtreeofagraphG,andletT’beanarbitraryspanningtreeofG,supposetheedgesofeachtreearesortedinnon-decreasingorder,thatis,w(e1)w(e2)…w(en-1)andw(e1’)w(e2’)…w(en-1’),thenfor1in-1,w(ei)w(ei’).Property4LetTbeaminimumspanningtreeofagraphG,andletLbethesortedlistoftheedgeweightsofT,thenforanyotherminimumspanningtreeT’ofG,thelistLisalsothesortedlistofedgeweightsofT’.PropertiesofMSTProperty3PropertiesofMSTProperty5Lete=(u,v)beamaximum-weightedgeonsomecycleofG.Provethatthereisaminimumspanningtreethatdoesnotincludee.Proof.ArbitrarilychooseaMSTT.IfTdoesnotcontaine,itisproved.Otherwise,T\eisdisconnected,andsupposeX,YarethetwoconnectedcomponentsofT\e.LeteisoncycleCinG.LetP=C\e.Thenthereisanedge(x,y)onPsuchthatxX,andy

Y.Andw(x,y)w(e).T’=T\e+(x,y)isaspanningtreeandw(T’)w(T).Alsowehavew(T)w(T’),sow(T’)=w(T).T’isaMSTnotincludinge.PropertiesofMSTProperty5BottleneckSpanningTreeAbottleneckspanningtree

Tofaconnected,weightedandundirectedgraphGisaspanningtreeofGwhoselargestedgeweightisminimumoverallspanningtreesofG.LetT1,T2,…,TmareallthespanningtreesofG,andthelargestedgeofeachtreeiset1,et2,…,etm,supposew(eti)w(etj)for1jmandji,thenTi

is

abottleneckspanningtree.ThevalueofaBSTTistheweightofthemaximum-weightedgeinT.Thebottleneckspanningtreemaynotbeunique.BottleneckSpanningTreeAbottBSTvsMSTEveryminimumspanningtreeisabottleneckspanningtree.Property4impliesit.Aneasierproof:LetTbeaMSTandT’beaBST,letthemaximum-weightedgeinTandT’beeande’,respectively.SupposeforthecontrarythattheMSTTisnotaBST,thenwehavew(e)>w(e’),whichalsoindicatesthattheweightofeisgreaterthanthatofanyedgesinT’.RemovingefromTdisconnectsTintotwosubtreesT1andT2,theremustexistanedgefinT’connectingT1andT2,otherwise,Tisnotconnected.T1T2{f}formsanewtreeT’’withw(T’’)=w(T)-w(e)+w(f)<

w(T),AcontradictiontothefactthatTisMST,thus,AMSTisalsoaBST.BSTvsMSTEveryminimumspanniGreedyAlgorithms(I)Greed,forlackofabetterword,isgood!Greedisright!Greedworks!-MichaelDouglas,U.S.actorintheroleofGordonGecko,inthefilmWallStreet,1987GreedyAlgorithms(I)Greed,foMaintopicsIdeaofthegreedyapproachChange-makingproblemMinimumspanningtreeproblemPrim’salgorithmKruskal’salgorithmPropertiesofminimumspanningtree(additivepart)Bottleneckspanningtree(additivepart)MaintopicsIdeaofthegreedyExpectedOutcomesStudentshouldbeabletosummarizetheideaofthegreedytechniquelistseveralapplicationsofthegreedytechniqueapplythegreedytechniquetochange-makingproblemdefinetheminimumspanningtreeproblemdescribeideasofPrimandKruskal’salgorithmsforcomputingminimumspanningtreeprovethecorrectnessofthetwoalgorithmsanalyzethetimecomplexitiesofthetwoalgorithmsunderdifferentdatastructuresprovethevariouspropertiesofminimumspanningtreeExpectedOutcomesStudentshoulGlossaryGreedy:貪婪的Change-makingproblem:找零錢問題Cashier:收銀員Denomination:貨幣單位，面額Quarter,dime,nickel,penny:2角5分，1角，5分，1分（美國硬幣單位）Irrevocable：不可取消的，不可逆的Spanningtree:生成樹，支撐樹GlossaryGreedy:貪婪的AnticipatorySet:

ChangeMakingProblemHowtomake48centsofchangeusingcoinsofdenominationsof25(1quartercoin),10(1dimecoin),5(1nickelcoin),and1(1pennycoin)sothatthetotalnumberofcoinsisthesmallest?Theidea:Takethecoinwithlargestdenominationwithoutexceedingtheremainingamountofcents,makethelocallybestchoiceateachstep.Isthesolutionoptimal?Yes,theproofisleftasexercise.AnticipatorySet:

ChangeMakiGeneralChange-MakingProblemGivenunlimitedamountsofcoinsofdenominationsd1>…>dm,givechangeforamountnwiththeleastnumberofcoins.Doesthegreedyalgorithmalwaysgiveanoptimalsolutionforthegeneralchange-makingproblem?Wegivethefollowingexample,Example:d1=7c,d2=5c,d3=1c,andn=10c,notalwaysproducesanoptimalsolution.infact,forsomeinstances,theproblemmaynothaveasolutionatall!considerinstanced1=7c,d2=5c,d3=3c,andn=11c.But,thisproblemcanbesolvedbydynamicprogramming,pleasetrytodesignanalgorithmforthegeneralchange-makingproblemafterclass.GeneralChange-MakingProblemGGreedyAlgorithmsAgreedyalgorithmmakesalocallyoptimalchoicestepbystepinthehopethatthischoicewillleadtoagloballyoptimalsolution.

Thechoicemadeateachstepmustbe:FeasibleSatisfytheproblem’sconstraintslocallyoptimalBethebestlocalchoiceamongallfeasiblechoicesIrrevocableOncemade,thechoicecan’tbechangedonsubsequentsteps.Dogreedyalgorithmsalwaysyieldoptimalsolutions?Example:changemakingproblemwithadenominationsetof7,5and1,andn=10?GreedyAlgorithmsAgreedyalgoApplicationsoftheGreedyStrategyOptimalsolutions:someinstancesofchangemakingMinimumSpanningTree(MST)Single-sourceshortestpathsHuffmancodesApproximations:TravelingSalesmanProblem(TSP)KnapsackproblemotheroptimizationproblemsForsomeproblems,yieldsanoptimalsolutionforeveryinstance.Formost,doesnotbutcanbeusefulforfastapproximations.ApplicationsoftheGreedyStrMinimumSpanningTree(MST)SpanningtreeofaconnectedgraphGisaconnectedacyclicsubgraph(tree)ofGthatincludesallofG’svertices.Note:aspanningtreewithnverticeshasexactlyn-1edges.MinimumSpanningTreeofaweighted,connectedgraphGisaspanningtreeofGofminimumtotalweight.Example:MinimumSpanningTree(MST)SpaMSTProblemGivenaconnected,undirected,weightedgraphG=(V,E),findaminimumspanningtreeforit.ComputeMSTthroughBruteForce?Kruskal:1956,Prim:1957BruteforceGenerateallpossiblespanningtreesforthegivengraph.Findtheonewithminimumtotalweight.FeasibilityofBruteforcePossibletoomanytrees(exponentialfordensegraphs)MSTProblemGivenaconnected,ThePrim’sAlgorithmIdeaofthePrim’salgorithmPseudo-codeofthealgorithmCorrectnessofthealgorithm(important)TimecomplexityofthealgorithmThePrim’sAlgorithmIdeaofthIdeaofPrimGrowasingletreebyrepeatedlyaddingtheleastcostedge(greedystep)thatconnectsavertexintheexistingtreetoavertexnotintheexistingtreeIntermediatesolutionisalwaysasubtreeofsomeminimumspanningtree.IdeaofPrimGrowasingletreePrim’sMSTalgorithmStartwithatree,T0,consistingofonevertex“Grow”treeonevertex/edgeatatimeConstructaseriesofexpandingsubtreesT1,T2,…Tn-1..AteachstageconstructTifromTi-1byaddingtheminimumweightedgethatconnectingavertexintree(Ti-1)toavertexnotyetinthetreethisisthe“greedy”step!AlgorithmstopswhenallverticesareincludedPrim’sMSTalgorithmStartwithPseudocodeofthePrimALGORITHMPrim(G)//Prim’salgorithmforconstructingaminimumspanningtree//Input:AweightedconnectedgraphG=(V,E)//Output:ET,thesetofedgescomposingaminimumspanningtreeofGVT{v0}//v0canbearbitrarilyselectedETfor

i1to|V|-1dofindaminimum-weightedgee*=(v*,u*)amongalltheedges(v,u)suchthatvisinVTanduisinV-VT

VTVT{u*}

ETET{e*}return

ETPseudocodeofthePrimALGORITHAnexampleaedcb1524637Anexampleaedcb1524637ThePrim’salgorithmisgreedy!Thechoiceofedgesaddedtocurrentsubtreesatisfyingthethreepropertiesofgreedyalgorithms.Feasible,eachedgeaddedtothetreedoesnotresultinacycle,guaranteethatthefinalETisaspanningtreeLocaloptimal,eachedgeselectedtothetreeisalwaystheonewithminimumweightamongalltheedgescrossingVTandV-VTIrrevocable,onceanedgeisaddedtothetree,itisnotremovedinsubsequentsteps.ThePrim’salgorithmisgreedyCorrectnessofPrimProvebyinductionthatthisconstructionprocessactuallyyieldsMST.T0isasubsetofallMSTsSupposethatTi-1isasubsetofsomeMSTT,weshouldprovethatTiwhichisgeneratedfromTi-1isalsoasubsetofsomeMST.Bycontradiction,assumethatTidoesnotbelongtoanyMST.Letei=(u,v)betheminimumweightedgefromavertexinTi-1toavertexnotinTi-1usedbyPrim’salgorithmtoexpandingTi-1toTi,accordingtoourassumption,eicannotbelongtoMSTT.AddingeitoTresultsinacyclecontaininganotheredgee’=(u’,v’)connectingavertexu’inTi-1toavertexv’notinit,andw(e’)w(ei)accordingtothegreedyPrim’salgorithm.Removinge’fromTandaddingeitoTresultsinanotherspanningtreeT’withweightw(T’)w(T),indicatingthatT’isaminimumspanningtreeincludingTiwhichcontradicttoassumptionthatTidoesnotbelongtoanyMST.CorrectnessofPrimProvebyinCorrectnessofPrimCorrectnessofPrimImplementationofPrimHowtoimplementthestepsinthePrim’salgorithm?Firstidea,labeleachvertexwitheither0or1,1representsthevertexinVT,and0otherwise.Traversetheedgesettofindanminimumweightedgewhoseendpointshavedifferentlabels.Timecomplexity:O(VE)ifadjacencylinkedlistandO(V3)foradjacencymatrixForsparsegraphs,useadjacencylinkedlistAnyimprovement?ImplementationofPrimHowtoiNotationsT:theexpandingsubtree.Q:theremainingvertices.Ateachstage,thekeypointofexpandingthecurrentsubtreeTistoDeterminewhichvertexinQisthenearestvertextoT.Qcanbethoughtofasapriorityqueue:Thekey(priority)ofeachvertex,key[v],meanstheminimumweightedgefromvtoavertexinT.Key[v]is∞ifvisnotlinkedtoanyvertexinT.Themajoroperationistotofindanddeletethenearestvertex(v,forwhichkey[v]isthesmallestamongallthevertices)RemovethenearestvertexvfromQandadditandthecorrespondingedgetoT.Withtheoccurrenceofthataction,thekeyofv’sneighborswillbechanged.ToremembertheedgesoftheMST,anarray[]isintroducedtorecordtheparentofeachvertex.Thatis[v]isthevertexintheexpandingsubtreeTthatisclosesttovnotinT.NotationsT:theexpandingsubtAdvancedPrim’sAlgorithmALGORITHMMST-PRIM(G,w,r)//w:weight;r:root,thestartingvertexforeachu

V[G]

do

key[u]

[u]NIL

//[u]:theparentofukey[r]0QV[G] //Nowthepriorityqueue,Q,hasbeenbuilt.while

Q

douExtract-Min(Q)//removethenearestvertexfromQ

foreachvAdj[u]//updatethekeyforeachofv’sadjacentnodes.

do

if

vQandw(u,v)<key[v]

then

[v]ukey[v]w(u,v)AdvancedPrim’sAlgorithmALGO國外算法設(shè)計與分析課件2TimeComplexityofPrim’salgorithmNeedpriorityqueueforlocatingthenearestvertexUseunorderedarraytostorethepriorityqueue: Efficiency:Θ(n2)Usebinarymin-heaptostorethepriorityqueue Efficiency:Forgraphwithnverticesandmedges:

O(mlogn)UseFibonacci-heaptostorethepriorityqueue:Efficiency:Forgraphwithnverticesandmedges:

O(nlogn+m)TimeComplexityofPrim’salgoKruskal’sMSTAlgorithmEdgesareinitiallysortedbyincreasingweightStartwithanemptyforestF0“grow”MSToneedgeatatimethroughaseriesofexpandingforestsF1,F2,…,Fn-1intermediatestagesusuallyhaveforestoftrees(notconnected)ateachstageaddminimumweightedgeamongthosenotyetusedthatdoesnotcreateacycleneedefficientwayofdetecting/avoidingcyclesalgorithmstopswhenallverticesareincludedKruskal’sMSTAlgorithmEdgesaCorrectnessofKruskalSimilartotheproofofPrimProvebyinductionontheconstructionprocessactuallygenerateaMSTConsiderF0,F1,…,Fn-1CorrectnessofKruskalSimilarBasicKruskal’sAlgorithmALGORITHMKruscal(G)//Input:AweightedconnectedgraphG=<V,E>

//Output:ET,thesetofedgescomposingaminimumspanningtreeofG.SortEinnondecreasingorderoftheedgeweightsw(ei1)<=…<=w(ei|E|) ET

;ecounter

0

//initializethesetoftreeedgesanditssizek0

whileencounter<|V|-1

do kk+1

ifET

U{eik}isacyclic

ET

ETU{eik};ecounterecounter+1returnETBasicKruskal’sAlgorithmALGORKruskal’sAlgorithm(AdvancedPart)Kruskal’sAlgorithm(Advanced國外算法設(shè)計與分析課件2Kruskal:TimeComplexity

O(EV)whendisjoint-setdatastructurearenotused.Whenusedisjoint-setdatastructurewithunion-by-rankandpath-compressionheuristics:InitializingthesetAinline1takesO(1)time.

O(V)MAKE-SEToperationsinlines2-3Sorttheedgesinline4takesO(ElogE)time.Theforloopoflines5-8performsO(E)FIND-SETandUNIONoperationsonthedisjoint-setforestb)andd)takeatotalofO((V+E)(V))Line9:O(V+E)Notethat:E

V-1and(V)=O(logV)=O(logE)andEV2SOtotaltimeis:O(ElogV)Kruskal:TimeComplexityO(EV)PropertiesofMSTProperty1:Let(u,v)beaminimum-weightedgeinagraphG=(V,E),then(u,v)belongstosomeminim