算法分析與設(shè)計第二版英文版(潘彥著)清華大學出版社課后答案-solu9

This?lecontainstheexercises,hints,andsolutionsforChapter9ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms,”2ndedition,byA.Levitin.Theproblemsthatmightbechallengingforatleastsomestudentsaremarkedby;thosethatmightbedi?cultforamajorityofstudentsaremarkedby.Exercises9.11.Giveaninstanceofthechange-makingproblemforwhichthegreedyal-gorithmdoesnotyieldanoptimalsolution.2.Writeapseudocodeofthegreedyalgorithmforthechange-makingprob-lem,withanamountnandcoindenominationsd1>d2>...>dasitsminput.Whatisthetimee?ciencyclassofyouralgorithm?3.Considertheproblemofschedulingnjobsofknowndurationst1,...,tfornexecutionbyasingleprocessor.Thejobscanbeexecutedinanyorder,onejobatatime.Youwantto?ndaschedulethatminimizesthetotaltimespentbyallthejobsinthesystem.(Thetimespentbyonejobinthesystemisthesumofthetimespentbythisjobinwaitingplusthetimespentonitsexecution.)Designagreedyalgorithmforthisproblem.rithmalwaysyieldanoptimalsolution?Doesthegreedyalgo-4.Designagreedyalgorithmfortheassignmentproblem(seeSection3.4).Doesyourgreedyalgorithmalwaysyieldanoptimalsolution?5.BridgecrossingrevisitedConsiderthegeneralizationofthebridgecross-ingpuzzle(Problem2inExercises1.2)inwhichwehaven>1peoplewhosebridgecrossingtimesaret1,t2,...,t.Alltheotherconditionsofntheproblemremainthesame:atmosttwopeopleatthetimecancrossthebridge(andtheymovewiththespeedoftheslowerofthetwo)andtheymustcarrywiththemtheonly?ashlightthegrouphas.Designagreedyalgorithmforthisproblemand?ndhowlongitwilltaketocrossthebridgebyusingthisalgorithm.Doesyouralgorithmyieldsaminimumcrossingtimeforeveryinstanceoftheproblem?Ifitdoes–proveit,ifitdoesnot–?ndaninstancewiththesmallestnumberofpeopleforwhichthishappens.6.Bachet-FibonacciweighingproblemFindanoptimalsetofnweights{w1,w2,...,w}sothatitwouldbepossibletoweighonabalancescalenanyintegerloadinthelargestpossiblerangefrom1toW,provideda.weightscanbeputonlyonthefreecupofthescale.b.weightscanbeputonbothcupsofthescale.1

7.a.ApplyPrim’salgorithmtothefollowinggraph.Includeinthepriorityqueuealltheverticesnotalreadyinthetree.5ab2435e76cd4b.ApplyPrim’salgorithmtothefollowinggraph.Includeinthepriorityqueueonlythefringevertices(theverticesnotinthecurrenttreewhichareadjacenttoatleastonetreevertex).3ab564345231623cdeif5457ghj69kl88.Thenotionofaminimumspanningtreeisapplicabletoaconnectedweightedgraph.Dowehavetocheckagraph’sconnectivitybeforeap-plyingPrim’salgorithmorcanthealgorithmdoitbyitself?9.a.HowcanweusePrim’salgorithmto?ndaspanningtreeofaconnectedgraphwithnoweightsonitsedges?b.Isitagoodalgorithmforthisproblem?10.Provethatanyweightedconnectedgraphwithdistinctweightshasexactlyoneminimumspanningtree.11.Outlineane?cientalgorithmforchanginganelement’svalueinamin-heap.Whatisthetimee?ciencyofyouralgorithm?2HintstoExercises9.11.Ascoindenominationsforyourcounterexample,youmayuse,amongamultitudeofotherpossibilities,theonesmentionedinthetext:d1=7,d2=5,d3=1.2.Youmayuseintegerdivisionsinyouralgorithm.3.Consideringthecaseoftwojobsmighthelp.Ofcourse,afterformingahypothesis,youwillhavetoeitherprovethealgorithm’soptimalityforanarbitraryinputor?ndaspeci?ccounterexampleshowingthatitisnotthecase.4.Youcanapplythegreedyapproacheithertotheentirecostmatrixortoeachofitsrows(orcolumns).5.Simplyapplythegreedyapproachtothesituationathand.Youmayassumethatt≤t≤...≤tn.126.Forbothversionsoftheproblem,itisnotdi?culttogettoahypothesisaboutthesolution’sformafterconsideringthecasesofn=1,2,and3.Itisprovingthesolutions’optimalitythatisattheheartofthisproblem.7.a.Tracethealgorithmforthegraphgiven.Anexamplecanbefoundinthetextofthesection.b.Afterthenextfringevertexisaddedtothetree,addalltheunseenverticesadjacenttoittothepriorityqueueoffringevertices.8.ApplyingPrim’salgorithmtoaweightedgraphthatisnotconnectedshouldhelpinansweringthisquestion.9.a.SincePrim’salgorithmneedsweightsonagraph’sedges,someweightshavetobeassigned.b.Doyouknowotheralgorithmsthatcansolvethisproblem?10.Strictlyspeaking,thewordingofthequestionasksyoutoprovetwothings:thefactthatatleastoneminimumspanningtreeexistsforanyweightedconnectedgraphandthefactthataminimumspanningtreeisuniqueifalltheweightsaredistinctnumbers.Theproofoftheformerstemsfromtheobviousobservationabout?nitenessofthenumberofspanningtreesforaweightedconnectedgraph.TheproofofthelattercanbeobtainedbyrepeatingthecorrectnessproofofPrim’salgorithmwithaminoradjustmentattheend.11.Considertwocases:thekey’svaluewasdecreased(thisisthecaseneededforPrim’salgorithm)andthekey’svaluewasincreased.3

SolutionstoExercises9.11.Hereisoneofmanysuchinstances:Forthecoindenominationsd1=7,d2=5,d3=1andtheamountn=10,thegreedyalgorithmyieldsonecoinofdenomination7andthreecoinsofdenomination1.Theactualoptimalsolutionistwocoinsofdenomination5.2.AlgorithmChange(n,D[1..m])//Implementsthegreedyalgorithmforthechange-makingproblem//Input:Anonnegativeintegeramountnand//adecreasingarrayofcoindenominationsD//Output:ArrayC[1..m]ofthenumberofcoinsofeachdenominationinthechangeorthe”nosolution”message//fori←1tomdoC[i]←n/D[i]n←nmodD[i]ifn=0returnCelsereturn”nosolution”Thealgorithm’stimee?ciencyisinΘ(m).(Weassumethatintegerdi-visionstakeaconstanttimenomatterhowbigdividendsare.)Notealsothatifwestopthealgorithmassoonastheremainingamountbecomes0,thetimee?ciencywillbeinO(m).3.a.Sortthejobsinnondecreasingorderoftheirexecutiontimesandexe-cutetheminthatorder.b.Yes,thisgreedyalgorithmalwaysyieldsanoptimalsolution.Indeed,foranyordering(i.e.,permutation)ofthejobsi1,i2,...,in,thetotaltimeinthesystemisgivenbytheformulat+(ti+ti)+...+(ti+t+...+ti)=nti+(n?1)ti+...+ti.iiThus,wehaveasumofnumbersn,n?1,...,1multipliedby“weights”t,1t,2...tnassignedtothenumbersinsomeorder.Tominimizesuchasum,wehavetoassignsmallert’stolargernumbers.Inotherwords,thejobsshouldbeexecutedinnondecreasingorderoftheirexecutiontimes.Hereisamoreformalproofofthisfact.Wewillshowthatifjobsareex-ecutedinsomeorderi1,i2,...,in,inwhicht>tforsomek,thentheiitotaltimeinthesystemforsuchanorderingcanbedecreased.(Hence,nosuchorderingcanbeanoptimalsolution.)Letusconsidertheotherjobordering,whichisobtainedbyswappingthejobskandk+1.Obvi-ously,thetimeinthesystemswillremainthesameforallbutthesetwo4

jobs.Therefore,thedi?erencebetweenthetotaltimeinthesystemfortheneworderingandtheonebeforetheswapwillbek?1[(k?1j=1k?1j=1k?1ti+ti)+(t+t)+(t+t+ti)]?[(t+t+t)]iiiiiiij=1=ti?t<0.j=1i4.a.Theall-matrixversion:Repeatthefollowingoperationntimes.Selectthesmallestelementintheunmarkedrowsandcolumnsofthecostmatrixandthenmarkitsrowandcolumn.Therow-by-rowversion:Startingwiththe?rstrowandendingwiththelastrowofthecostmatrix,selectthesmallestelementinthatrowwhichisnotinapreviouslymarkedcolumn.Aftersuchanelementisselected,markitscolumntopreventselectinganotherelementfromthesamecol-umn.b.Neitheroftheversionsalwaysyieldsanoptimalsolution.Hereisasimplecounterexample:121002C=5.Repeatthefollowingstepn?2times:Sendtotheothersidethepairoftwofastestremainingpersonsandthenreturnthe?ashlightwiththefastestperson.Finally,sendtheremainingtwopeopletogether.Assumingthatt≤t≤...≤tn,thetotalcrossingtimewillbeequalto12nn(t2+t1)+(t3+t1)+...+(tn?1+t1)+tn=ti+(n?2)t1=ti+(n?3)t.1i=2i=1Note:Foranalgorithmthatalwaysyieldsaminimalcrossingtime,seeGünterRote,“CrossingtheBridgeatNight,”EATCSBulletin,vol.78(October2002),241—246.ThesolutiontotheinstanceofProblem2inExercises1.2showsthatthegreedyalgorithmdoesn’talwaysyieldtheminimalcrossingtimeforn>3.Nosmallercounterexamplecanbegivenasasimpleexhaustivecheckforn=3demonstrates.(Theobvioussolutionforn=2istheonegeneratedbythegreedyalgorithmaswell.)5

6.a.Let’sapplythegreedyapproachtothe?rstfewinstancesoftheprobleminquestion.Forn=1,wehavetousew1=1tobalanceweight1.Forn=2,wesimplyaddw2=2tobalancethe?rstpreviouslyunattainableweightof2.Theweights{1,2}canbalanceeveryintegralweightsuptotheirsum3.Forn=3,inthespiritofgreedythinking,wetakethenextpreviouslyunattainableweight:w3=4.Thethreeweights{1,2,4}allowtoweighanyintegralloadlbetween1andtheirsum7,withl’sbinaryexpansionindicatingtheweightsneededforloadl:loadll’sbinaryexpansion110weightsforloadl123112+141001014561107111124+14+24+2+1Generalizingtheseobservations,weshouldhypothesizethatforanyposi-tiveintegernthesetofconsecutivepowersof2{wi=2i?1,i=1,2,...n}makesitpossibletobalanceeveryintegralloadinthelargestpossiblerange,whichisuptoandincludingn2i?1=2n?1.Thefactthati=1everyintegralweightlintherange1≤l≤2n?1canbebalancedwiththissetofweightsfollowsimmediatelyfromthebinaryexpansionofl,whichyieldstheweightsneededforweighingl.(Notethatwecanobtaintheweightsneededforagivenloadlbyapplyingtoitthegreedyalgorithmforthechange-makingproblemwithdenominationsdi=2i?1,i=1,2,...n.)Inordertoprovethatnosetofnweightscancoveralargerrangeofconsecutiveintegralloads,itwillsu?cetonotethattherearejust2n?1nonemptyselectionsofnweightsand,hence,nomorethan2n?1sumstheyyield.Therefore,thelargestrangeofconsecutiveintegralloadstheycancovercannotexceed2n?1.[Alternatively,toprovethatnosetofnweightscancoveralargerrangeofconsecutiveintegralloads,wecanprovebyinductiononithatifanymul-tisetofnweights{wi,i=1,...,n}–whichwecanassumewithoutlossofgeneralitytobesortedinnondecreasingorder–canbalanceeveryintegralloadstartingwith1,thenwi≤2i?1fori=1,2,...,n.Thebasischecksoutimmediately:w1mustbe1,whichisequalto21?1.Forthegeneralcase,assumethatwk≤2k?1forevery1≤k<i.Thelargestweightthe?rsti?1weightscanbalanceisi?1wk≤wiwerelargerthan2i,thenthisloadcouldhavebeenbalancedneitheri?12k?1=2i?1?1.Ifk=1k=1withthe?rsti?1weights(whicharetoolighteventakentogether)norwiththeweightswi≤...≤wn(whichareheavierthan2ievenindivid-ually).Hence,wi≤2i?1,whichcompletestheproofbyinduction.Thisimmediatelyimpliesthatnonweightscanbalanceeveryintegralloaduptotheupperlimitlargerthannwi≤attainablewiththeconsecutivepowersof2weights.]n2i?1=2n?1,thelimiti=1i=1b.Ifweightscanbeputonbothcupsofthescale,thenalargerrangecan6bereachedwithnweightsforn>1.(Forn=1,thesingleweightstillneedstobe1,ofcourse.)Theweights{1,3}enableweighingofeveryintegralloadupto4;theweights{1,3,9}enableweighingofeveryinte-gralloadupto13,and,ingeneral,theweights{wi=3i?1,i=1,2,...,n}enableweighingofeveryintegralloaduptoandincludingtheirsumofn3i?1=(3n?1)/2.Aload’sexpansionintheternarysystemindicatesi=1theweightsneeded.Iftheternaryexpansioncontainsonly0’sand1’s,theloadrequiresputtingtheweightscorrespondingtothe1’sontheoppositecupofthebalance.Iftheternaryexpansionofloadl,l≤(3n?1)/2,containsoneormore2’s,wecanreplaceeach2by(3-1)torepresentitintheformnl=β3i?1,whereβ∈{0,1,?1},n=log(l+1).ii3i=1Infact,everypositiveintegercanbeuniquelyrepresentedinthisform,obtainedfromitsternaryexpansionasdescribedabove.Forexample,5=123=1·31+2·30=1·31+(3?1)·30=2·31?1·30=(3?1)·31?1·30=1·32?1·31?1·30.(Notethatifwestartwiththerightmost2,afterasimpli?cation,thenewrightmost2,ifany,willbeatsomepositiontotheleftofthestartingone.Thisprovesthataftera?nitenumberofsuchreplacements,wewillbeabletoeliminateallthe2’s.)Usingtherepresentationl=nβ3i?1,i=1iwecanweighloadlbyplacingalltheweightswi=3i?1fornegativeβ’sialongwiththeloadononecupofthescaleandalltheweightswi=3i?1forpositiveβ’sontheoppositecup.iNowwe’llprovethatnosetofnweightscancoveralargerrangeofcon-secutiveintegralloadsthan(3n?1)/2.Eachofthenweightscanbeeitherputontheleftcupofthescale,orputontherightcup,ornottobeusedatall.Hence,thereare3n?1possiblearrangementsoftheweightsonthescale,witheachofthemhavingitsmirrorimage(wherealltheweightsareswitchedtotheoppositepanofthescale).Eliminatingthissymmetry,leavesuswithjust(3n?1)/2arrangements,whichcanweightatmost(3n?1)/2di?erentintegralloads.Therefore,thelargestrangeofconsecutiveintegralloadstheycancovercannotexceed(3n?1)/2.7.a.ApplyPrim’salgorithmtothefollowinggraph:5acbd2435e7647TreeverticesPriorityqueueofremainingverticesa(-,-)e(a,2)b(e,3)c(e,4)d(c,4)b(a,5)c(a,7)d(a,∞)e(a,2)b(e,3)c(e,4)d(e,5)c(e,4)d(e,5)d(c,4)Theminimumspanningtreefoundbythealgorithmcomprisestheedgesae,eb,ec,andcd.b.ApplyPrim’salgorithmtothefollowinggraph:3ab564345231623cdeif5457ghj69kl8Treeverticesa(-,-)Priorityqueueoffringeverticesb(a,3)c(a,5)d(a,4)c(a,5)d(a,4)e(b,3)f(b,6)c(a,5)d(e,1)f(e,2)i(e,4)c(d,2)f(e,2)i(e,4)h(d,5)f(e,2)i(e,4)h(d,5)g(c,4)i(e,4)h(d,5)g(c,4)j(f,5)h(d,5)g(c,4)j(i,3)l(i,5)h(d,5)g(c,4)l(i,5)b(a,3)e(b,3)d(e,1)c(d,2)f(e,2)i(e,4)j(i,3)g(c,4)h(g,3)l(i,5)h(g,3)l(i,5)k(g,6)l(i,5)k(g,6)k(g,6)k(g,6)Theminimumspanningtreefoundbythealgorithmcomprisestheedgesab,be,ed,dc,ef,ei,ij,cg,gh,il,gk.8.Thereisnoneedtocheckthegraph’sconnectivitybecausePrim’salgo-rithmcandoititself.Ifthealgorithmreachesallthegraph’svertices(viaedgesof?nitelengths),thegraphisconnected,otherwise,itisnot.9.a.Thesimplestandmostlogicalsolutionistoassignalltheedgeweightsto1.8b.Applyingadepth-?rstsearch(orbreadth-?rstsearch)traversaltogetadepth-?rstsearchtree(orabreadth-?rstsearchtree),isconceptuallysimplerandforsparsegraphsrepresentedbytheiradjacencylistsfaster.10.Thenumberofspanningtreesforanyweightedconnectedgraphisapos-itive?nitenumber.(Atleastonespanningtreeexists,e.g.,theoneobtainedbyadepth-?rstsearchtraversalofthegraph.Andthenumberofspanningtreesmustbe?nitebecauseanysuchtreecomprisesasubsetofedgesofthe?nitesetofedgesofthegivengraph.)Hence,onecanalways?ndaspanningtreewiththesmallesttotalweightamongthe?nitenumberofthecandidates.Let’sprovenowthattheminimumspanningtreeisuniqueifalltheweightsaredistinct.We’lldothisbycontradiction,i.e.,byassumingthatthereexistsagraphG=(V,E)withalldistinctweightsbutwithmorethanoneminimumspanningtree.Lete1,...,e|V|?1bethelistofedgescom-posingtheminimumspanningtreeTPobtainedbyPrim’salgorithmwithsomespeci?cvertexasthealgorithm’sstartingpointandletTbean-otherminimumspanningtree.Letei=(v,u)bethe?rstedgeinthelistoftheedgesofTwhichisnotinT(ifTP=T,suchedgePe1,...,e|V|?1mustexist)andlet(v,u)beanedgeofTconnectingvwithavertexnotinthesubtreeTi?1formedby{e1,...,ei?1}(ifi=1,Ti?1consistsofvertexvonly).SimilarlytotheproofofPrim’salgorithmscorrectness,letusreplace(v,u)byei=(v,u)inT.Itwillcreateanotherspanningtree,whoseweightissmallerthantheweightofTbecausetheweightofei=(v,u)issmallerthantheweightof(v,u).(SinceeiwaschosenbyPrim’salgorithm,itsweightisthesmallestamongalltheweightsontheedgesconnectingthetreeverticesofthesubtreeTi?1andtheverticesadjacenttoit.Andsincealltheweightsaredistinct,theweightof(v,u)mustbestrictlygreaterthantheweightofei=(v,u).)ThiscontradictstheassumptionthatTwasaminimumspanningtree.11.Ifakey’svalueinamin-heapwasdecreased,itmayneedtobepushedup(viaswaps)alongthechainofitsancestorsuntilitissmallerthanorequaltoitsparentorreachestheroot.Ifakey’svalueinamin-heapwasincreased,itmayneedtobepusheddownbyswapswiththesmallerofitscurrentchildrenuntilitissmallerthanorequaltoitschildrenorreachesaleaf.Sincetheheightofamin-heapwithnnodesisequaltologn(by2thesamereasontheheightofamax-heapisgivenbythisformula–seeSection6.4),theoperation’se?ciencyisinO(logn).(Note:Theoldvalueofthekeyinquestionneednotbeknown,ofcourse.Comparingthenewvaluewiththatoftheparentand,ifthemin-heapconditionholds,withthesmallerofthetwochildren,willsu?ce.)9

Exercises9.21.ApplyKruskal’salgorithmto?ndaminimumspanningtreeofthefollow-inggraphs.a.1bc6534ade62b.3ab5643231623cdeif455457ghj69kl82.Indicatewhetherthefollowingstatementsaretrueorfalse:a.Ifeisaminimum-weightedgeinaconnectedweightedgraph,itmustbeamongedgesofatleastoneminimumspanningtreeofthegraph.b.Ifeisaminimum-weightedgeinaconnectedweightedgraph,itmustbeamongedgesofeachminimumspanningtreeofthegraph.c.Ifedgeweightsofaconnectedweightedgrapharealldistinct,thegraphmusthaveexactlyoneminimumspanningtree.d.Ifedgeweightsofaconnectedweightedgrapharenotalldistinct,thegraphmusthavemorethanoneminimumspanningtree.3.Whatchanges,ifany,needtobemadeinalgorithmKruskaltomakeit?ndaminimumspanningforestforanarbitrarygraph?(Aminimumspanningforestisaforestwhosetreesareminimumspanningtreesofthegraph’sconnectedcomponents.)104.WilleitherKruskal’sorPrim’salgorithmworkcorrectlyongraphsthathavenegativeedgeweights?5.Designanalgorithmfor?ndingamaximumspanningtree–aspanningtreewiththelargestpossibleedgeweight–ofaweightedconnectedgraph.6.RewritethepseudocodeofKruskal’salgorithmintermsoftheoperationsofthedisjointsubsets’ADT.7.ProvethecorrectnessofKruskal’salgorithm.8.Provethatthetimee?ciencyof?nd(x)isinO(logn)fortheunion-by-sizeversionofquickunion.9.FindatleasttwoWebsiteswithanimationsofKruskal’sandPrim’sal-gorithms.Discusstheirmeritsanddemerits..10.Designandconductanexperimenttoempiricallycomparethee?cienciesofPrim’sandKruskal’salgorithmsonrandomgraphsofdi?erentsizesanddensities.11.SteinertreeFourvillagesarelocatedattheverticesofaunitsquareintheEuclideanplane.Youareaskedtoconnectthembytheshortestnetworkofroadssothatthereisapathbetweeneverypairofthevillagesalongthoseroads.Findsuchanetwork.11

HintstoExercises9.21.Tracethealgorithmforthegivengraphsthesamewayitisdoneforanotherinputinthesection.2.Twoofthefourassertionsaretrue,theothertwoarefalse.3.ApplyingKruskal’salgorithmtoadisconnectedgraphshouldhelptoan-swerthequestion.4.Theansweristhesameforbothalgorithms.Ifyoubelievethatthealgorithmsworkcorrectlyongraphswithnegativeweights,provethisassertion;ityoubelievethisisnottobethecase,giveacounterexampleforeachalgorithm.5.Isthegeneraltrickoftransformingmaximizationproblemstotheirmini-mizationcounterparts(seeSection6.6)applicablehere?6.Substitutethethreeoperationsofthedisjointsubsets’ADT–makeset(x),?nd(x),andunion(x,y)–intheappropriateplacesofthepseudocodegiveninthesection.7.FollowtheplanusedinSection9.1toprovethecorrectnessofPrim’salgorithm.8.Theargumentisverysimilartotheonemadeinthesectionfortheunion-by-sizeversionofquick?nd.9.Youmaywanttotakeadvantageofthelistofdesirablecharacteristicsinalgorithmvisualizations,whichisgiveninSection2.7.10.n/a11.Thequestionisnottrivialbecauseintroducingextrapoints(calledSteinerpoints)maymakethetotallengthofthenetworksmallerthanthatofaminimumspanningtreeofthesquare.Solving?rsttheproblemforthreeequidistantpointsmightgiveyouanindicationhowasolutiontotheprobleminquestioncouldlooklike.12

SolutionstoExercises9.21.a.1bc6534ade62TreeSortedlistofedgesIllustrationedges(selectededgesareshowninbold)1bc6666bcdebdcdabadce5333344441234566aaaadeeee621bcbc1bcdebdcdabadce5551234566d621bcde2bcdebdcdabadce1234566d621bcbd3bcdebdcdabadce1234566d62ab513b.33abab5666566643454345231623231623cdeifcdeif???575554575554ghghjj69996999klkl8383?abab5543454345231623231623cdeifcdeif457457ghghjj66klkl8383?abab5543454345231623231623cdeifcdeif457457ghghjj66klkl88?1433abab5666566643454345231623231623cdeifcdeif???575554575554ghghjj69996999klkl8383?abab5543454345231623231623cdeifcdeif457457ghghjj66klkl8383?abab5543454345231623231623cdeifcdeif457457ghghjj66klkl882.a.True.(Otherwise,Kruskal’salgorithmwouldbeinvalid.)b.False.Asasimplecounterexample,consideracompletegraphwiththreeverticesandthesameweightonitsthreeedgesc.True(Problem10inExercises9.1).15d.False(see,forexample,thegraphofProblem1a).3.Sincethenumberofedgesinaminimumspanningforestofagraphwith|V|verticesand|C|connectedcomponentsisequalto|V|?|C|(thisfor-mulaisasimplegeneralizationof|E|=|V|?1forconnectedgraphs),Kruskal(G)willnevergetto|V|?1treeedgesunlessthegraphiscon-nected.Asimpleremedyistoreplacetheloopwhileecounter<|V|?1withwhilek<|E|tomakethealgorithmstopafterexhaustingthesortedlistofitsedges.4.Bothalgorithmsworkcorrectlyforgraphswithnegativeedgeweights.Onewayofshowingthisistoaddtoalltheweightsofagraphwithnegativeweightssomelargepositivenumber.Thismakesallthenewweightspositive,andonecan“translate”thealgorithms’actionsonthenewgraphtothecorrespondingactionsontheoldone.Alternatively,youcancheckthattheproofsjustifyingthealgorithms’correctnessdonotdependontheedgeweightsbeingnonnegative.5.Replaceeachweightw(u,v)by?w(u,v)andapplyanyminimumspanningtreealgorithmthatworksongraphswitharbitraryweights(e.g.,Prim’sorKruskal’salgorithm)tothegraphwiththenewweights.6.AlgorithmKruskal(G)//Kruskal’salgorithmwithexplicitdisjoint-subsetsoperations//Input:AweightedconnectedgraphG=V,E//Output:ET,thesetofedgescomposingaminimumspanningtreeofGsortEinnondecreasingorderoftheedgeweightsw(ei)≤...≤w(ei)foreachvertexv∈Vmake(v)ET←?;ecounter←0k←0//initializethesetoftreeedgesanditssize//thenumberofprocessededgeswhileecounter<|V|?1k←k+1if?nd(u)=?nd(v)//u,varetheendpointsofedgeei←E∪{e};ecounter←ecounter+1ETTiunion(u,v)returnET7.LetusprovebyinductionthateachoftheforestsFi,i=0,...,|V|?1,ofKruskal’salgorithmisapart(i.e.,asubgraph)ofsomeminimumspan-ningtree.(Thisimmediatelyimplies,ofcourse,thatthelastforestinthesequence,F|V|?1,isaminimumspanningtreeitself.Indeed,itcontainsallverticesofthegraph,anditisconnectedbecauseitisbothacyclicandhas|V|?1edges.)Thebasisoftheinductionistrivial,sinceF0is16

madeupof|V|single-vertextreesandthereforemustbeasubgraphofanyspanningtreeofthegraph.Fortheinductivestep,letusassumethatFi?1isasubgraphofsomeminimumspanningtreeT.WeneedtoprovethatFi,generatedfromFi?1byKruskal’salgorithm,isalsoapartofaminimumspanningtree.WeprovethisbycontradictionbyassumingthatnominimumspanningtreeofthegraphcancontainFi.Letei=(v,u)betheminimumweightedgeaddedbyKruskal’salgorithmtoforestFi?1toobtainforestFi.(Notethatverticesvandumustbelongtodi?erenttreesofFi?1–otherwise,edge(v,u)would’vecreatedacycle.)Byourassumption,eicannotbelongtoT.Therefore,ifweaddeitoT,acyclemustbeformed(seethe?gurebelow).Inadditiontoedgeei=(v,u),thiscyclemustcontainanotheredge(v,u)connectingavertexvinthesametreeofFi?1asvtoavertexunotinthattree.(Itispossiblethatvcoincideswithvorucoincideswithubutnotboth.)Ifwenowdeletetheedge(v,u)fromthiscycle,wewillobtainanotherspanningtreeoftheentiregraphwhoseweightislessthanorequaltotheweightofTsincetheweightofeiislessthanorequaltotheweightof(v,u).Hence,thisspanningtreeisaminimumspanningtree,whichcontr