372
Chapter8 TheDisjointSetsClass
8.7 AnApplication
Anexampleoftheuseoftheunion/finddatastructureisthegenerationofmazes,such
astheoneshowninFigure8.25.InFigure8.25,thestartingpointisthetop-leftcorner,
andtheendingpointisthebottom-rightcorner.Wecanviewthemazeasa50-by-88
rectangleofcellsinwhichthetop-leftcellisconnectedtothebottom-rightcell,andcells
areseparatedfromtheirneighboringcellsviawalls.
Asimplealgorithmtogeneratethemazeistostartwithwallseverywhere(exceptfor
theentranceandexit).Wethencontinuallychooseawallrandomly,andknockitdownif
thecellsthatthewallseparatesarenotalreadyconnectedtoeachother.Ifwerepeatthis
processuntilthestartingandendingcellsareconnected,thenwehaveamaze.Itisactually
bettertocontinueknockingdownwallsuntileverycellisreachablefromeveryothercell
(thisgeneratesmorefalseleadsinthemaze).
Weillustratethealgorithmwitha5-by-5maze.Figure8.26showstheinitialconfig-
uration.Weusetheunion/finddatastructuretorepresentsetsofcellsthatareconnected
toeach other.Initially,walls are everywhere,and each cellis in its own n equivalence
class.
Figure8.27showsalaterstageofthealgorithm,afterafewwallshavebeenknocked
down.Suppose,atthisstage,thewallthatconnectscells8and13israndomlytargeted.
Because8and13arealreadyconnected(theyareinthesameset),wewouldnotremove
thewall,asitwouldsimplytrivializethemaze.Supposethatcells18and13arerandomly
targetednext.Byperformingtwo
find
operations,weseethattheseareindifferentsets;
thus18and13arenotalreadyconnected.Therefore,weknockdownthewallthatsep-
aratesthem,asshowninFigure8.28.Noticethatasaresultofthisoperation,thesets
Figure8.25 A50-by-88maze
Converting pdf to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
image from pdf to powerpoint; convert pdf into ppt online
Converting pdf to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
change pdf to powerpoint on; adding pdf to powerpoint
8.7 AnApplication
373
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} {17} {18} {19} {20} {21}
{22} {23} {24}
Figure8.26 Initialstate:allwallsup,allcellsintheirownset
containing18and13arecombinedviaa
union
operation.Thisisbecauseeverythingthat
wasconnectedto18isnowconnectedtoeverythingthatwasconnectedto13.Attheend
ofthealgorithm,depictedinFigure8.29,everythingisconnected,andwearedone.
Therunningtimeofthealgorithmisdominatedbytheunion/findcosts.Thesizeof
theunion/finduniverseisequaltothenumberofcells.Thenumberof
find
operationsis
proportionaltothenumberofcells,sincethenumberofremovedwallsisonelessthan
thenumberofcells,whilewithcare,weseethatthereareonlyabouttwicethenumberof
wallsascellsinthefirstplace.Thus,ifNisthenumberofcells,sincetherearetwofinds
perrandomlytargetedwall,thisgivesanestimateofbetween(roughly)2Nand4N
find
operationsthroughoutthealgorithm.Therefore,thealgorithm’srunningtimecanbetaken
asO(Nlog
N),andthisalgorithmquicklygeneratesamaze.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{0, 1} {2} {3} {4, 6, 7, 8, 9, 13, 14} {5} {10, 11, 15} {12} {16, 17, 18, 22} {19} {20} {21} {23} {24}
Figure8.27 Atsomepointinthealgorithm:Severalwallsdown,setshavemerged;ifat
thispointthewallbetween8and13israndomlyselected,thiswallisnotknockeddown,
because8and13arealreadyconnected
C# powerpoint - PowerPoint Conversion & Rendering in C#.NET
This PowerPoint document converting library component offers reliable C#.NET PowerPoint document rendering APIs for developers PowerPoint to PDF Conversion.
convert pdf pages to powerpoint slides; how to add pdf to powerpoint presentation
C# powerpoint - Convert PowerPoint to PDF in C#.NET
Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint Why do we need this PowerPoint to PDF converting library? In
convert pdf pages into powerpoint slides; convert pdf file to powerpoint presentation
374
Chapter8 TheDisjointSetsClass
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{0, 1} {2} {3} {4, 6, 7, 8, 9, 13, 14, 16, 17, 18, 22} {5} {10, 11, 15} {12} {19} {20} {21} {23} {24}
Figure8.28 Wallbetweensquares18and13israndomlyselectedinFigure8.27;this
wall is s knocked down, , because 18 and d 13 are not already connected; ; their sets are
merged
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24}
Figure8.29 Eventually,24wallsareknockeddown;allelementsareinthesameset
Summary
We haveseen a very simpledatastructure to maintain disjointsets.When the
union
operationisperformed,itdoesnotmatter,asfarascorrectnessisconcerned,whichset
retains its name.Avaluablelessonthat should belearned here is that it can bevery
importanttoconsiderthealternativeswhenaparticularstepisnottotallyspecified.The
union
stepisflexible;bytakingadvantageofthis,weareabletogetamuchmoreefficient
algorithm.
Pathcompressionisoneoftheearliestformsofself-adjustment,whichwehaveseen
elsewhere(splaytrees,skewheaps).Itsuseisextremelyinteresting,especiallyfromathe-
oreticalpointofview,becauseitwasoneofthefirstexamplesofasimplealgorithmwitha
not-so-simpleworst-caseanalysis.
Online Convert PowerPoint to PDF file. Best free online export
Then just wait until the conversion from Powerpoint to PDF is complete and download the file Creating a PDF from PPTX/PPT has never been so easy Easy converting!
change pdf to ppt; pdf conversion to powerpoint
C# PDF Convert to HTML SDK: Convert PDF to html files in C#.net
Best C#.NET PDF Converter SDK for converting PDF to HTML in Visual Studio .NET. This is a C# programming example for converting PDF to HTML.
change pdf to powerpoint online; convert pdf to ppt
Exercises
375
Exercises
8.1
Showtheresultofthefollowingsequenceofinstructions:
union(1,2)
,
union(3,4)
,
union(3,5)
,
union(1,7)
,
union(3,6)
,
union(8,9)
,
union(1,8)
,
union(3,10)
,
union (3,11)
,
union(3,12)
,
union(3,13)
,
union(14,15)
,
union(16,0)
,
union(14,16)
,
union (1,3)
,
union(1,14)
whenthe
union
sare
a. performedarbitrarily
b.performedbyheight
c. performedbysize
8.2
Foreachofthetreesinthepreviousexercise,performa
find
withpathcompression
onthedeepestnode.
8.3
Writeaprogramtodeterminetheeffects ofpath compression andthe various
union
ingstrategies.Yourprogramshouldprocessalongsequenceofequivalence
operationsusingallsixofthepossiblestrategies.
8.4
Showthatif
union
sareperformedbyheight,thenthedepthofanytreeisO(logN).
8.5
Supposef(N)isanicelydefinedfunctionthatreducesNtoasmallerinteger.What
isthesolutiontotherecurrenceT(N)=
N
f(N)
T(f(N))+Nwithappropriateinitial
conditions?
8.6
a. ShowthatifM=N2,thentherunningtimeofMunion/findoperationsisO(M).
b.ShowthatifM=NlogN,thentherunningtimeofMunion/findoperationsis
O(M).
c. Suppose = (NloglogN). . What is the e running time e of union/find
operations?
d.Suppose = (Nlog
N). What t is s the e running time e of union/find
operations?
8.7
Tarjan’soriginalboundfortheunion/findalgorithmdefined
α(M,N)=min{i≥1|(A(i,M/N)>logN)},where
A(1,j)=2
j
j≥1
A(i,1)=A(i−1,2)
i≥2
A(i,j)=A(i−1,A(i,j−1))
i,j≥2
Here,A(m,n)isoneversionoftheAckermannfunction.Arethetwodefinitions
ofαasymptoticallyequivalent?
8.8
ProvethatforthemazesgeneratedbythealgorithminSection8.7,thepathfrom
thestartingtoendingpointsisunique.
8.9
Designanalgorithmthatgeneratesamazethatcontainsnopathfromstarttofinish
buthasthepropertythattheremovalofaprespecifiedwallcreatesauniquepath.
8.10
Supposewewanttoaddanextraoperation,
deunion
,whichundoesthelast
union
operationthathasnotbeenalreadyundone.
a. Showthatifwedounion-by-heightand
find
swithoutpathcompression,then
deunion
iseasy,andasequenceofM
union
,
find
,and
deunion
operationstakes
O(MlogN)time.
b.Whydoespathcompressionmake
deunion
hard?
VB.NET PDF Converter Library SDK to convert PDF to other file
This guide give a series of demo code directly for converting MicroSoft Office Word, Excel and PowerPoint document to PDF file in VB.NET application.
convert pdf slides to powerpoint; online pdf converter to powerpoint
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
Converting PowerPoint document to PDF file can be quite simple provided that this VB.NET PowerPoint Converting SDK is correctly installed and utilized.
converting pdf to powerpoint; how to add pdf to powerpoint
376
Chapter8 TheDisjointSetsClass

c. Show how to implement all three operations so that the sequence of M
operationstakesO(MlogN/loglogN)time.
8.11
Supposewewanttoaddanextraoperation,
remove(x)
,whichremoves
x
fromits
currentsetandplacesitinitsown.Showhowtomodifytheunion/findalgorithm
sothattherunningtimeofasequenceofM
union
,
find
,and
remove
operationsis
O(Mα(M,N)).
8.12 Showthatifallofthe
union
sprecedethe
find
s,thenthedisjointsetsalgorithmwith
pathcompressionrequireslineartime,evenifthe
union
saredonearbitrarily.

8.13 Provethatif
union
saredonearbitrarily,butpathcompressionisperformedonthe
find
s,thentheworst-caserunningtimeis(MlogN).
8.14 Provethatif
union
saredonebysizeandpathcompressionisperformed,theworst-
caserunningtimeisO(Mα(M,N)).
8.15 ThedisjointsetanalysisinSection8.6canberefinedtoprovidetightboundsfor
smallN.
a. ShowthatC(M,N,0)andC(M,N,1)areboth0.
b.ShowthatC(M,N,2)isatmostM.
c. Letr≤8.Chooses=2andshowthatC(M,N,r)isatmostM+N.
8.16 Supposeweimplementpartialpathcompressionon
find(i)
bymakingeveryother
nodeonthepathfromitotherootlinktoitsgrandparent(wherethismakessense).
Thisisknownaspathhalving.
a. Writeaproceduretodothis.
b.Provethatifpathhalvingisperformedonthe
find
sandeitherunion-by-height
orunion-by-sizeisused,theworst-caserunningtimeisO(Mα(M,N)).
8.17 Writea programthatgeneratesmazesofarbitrarysize.Ifyou areusinga sys-
temwithawindowingpackage,generateamazesimilartothatin Figure8.25.
Otherwisedescribeatextualrepresentationofthemaze(forinstance,eachlineof
outputrepresentsasquareandhasinformationaboutwhichwallsarepresent)and
haveyourprogramgeneratearepresentation.
References
Varioussolutionstotheunion/findproblemcanbefoundin[6],[9],and[11].Hopcroft
andUllmanshowedanO(Mlog
N)boundusinganonrecursivedecomposition.Tarjan
[16]obtainedthebound O(Mα(M,N)),whereα(M,N)isasdefinedin Exercise8.7.A
moreprecise(butasymptoticallyidentical)boundforM<Nappearsin[2]and[19].The
analysisinSection8.6isduetoSeidelandSharir[15].Variousotherstrategiesforpath
compressionand
union
salsoachievethesamebound;see[19]fordetails.
Alowerboundshowingthatundercertainrestrictions(Mα(M,N))timeisrequired
toprocessMunion/findoperationswasgivenbyTarjan[17].Identicalboundsunderless
restrictiveconditionshavebeenshownin[7]and[14].
Applicationsoftheunion/finddatastructureappearin[1]and[10].Certainspecial
casesoftheunion/findproblemcanbesolvedinO(M)time[8].Thisreducestherunning
timeofseveralalgorithms,suchas[1],graphdominance,andreducibility(seereferences
C# PDF Converter Library SDK to convert PDF to other file formats
Free C#.NET SDK library and components for converting PDF file in .NET Windows applications, ASP.NET web programs and .NET console application.
how to convert pdf to powerpoint; picture from pdf to powerpoint
C# PDF Convert to Word SDK: Convert PDF to Word library in C#.net
Word in C#.NET. Online C#.NET Tutorial for Converting PDF to Word (.doc/ .docx) Document with .NET XDoc.PDF Library in C#.NET Class.
converting pdf to ppt; convert pdf to powerpoint slides
References
377
in Chapter9)byafactorofα(M,N).Others,suchas[10]and thegraphconnectivity
probleminthischapter,areunaffected.Thepaperlists10examples.Tarjanhasusedpath
compressiontoobtainefficientalgorithmsforseveralgraphproblems[18].
Average-caseresults fortheunion/findproblemappearin[5],[12],[22],and[3].
Resultsbounding the running time of any singleoperation (as opposed tothe entire
sequence)appearin[4]and[13].
Exercise 8.10 is solved in [21]. A general union/find d structure, supporting more
operations,isgivenin[20].
1.A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,“OnFindingLowestCommonAncestorsin
Trees,”SIAMJournalonComputing,5(1976),115–132.
2.L. Banachowski, “A Complement t to o Tarjan’s Result t about the Lower r Bound on the
ComplexityoftheSetUnionProblem,”InformationProcessingLetters,11(1980),59–65.
3.B.BollobásandI.Simon,“ProbabilisticAnalysisofDisjointSetUnionAlgorithms,”SIAM
JournalonComputing,22(1993),1053–1086.
4.N.Blum,“OntheSingle-OperationWorst-CaseTimeComplexityoftheDisjointSetUnion
Problem,”SIAMJournalonComputing,15(1986),1021–1024.
5.J. Doyle andR. L. Rivest, “LinearExpectedTime of a Simple UnionFindAlgorithm,”
InformationProcessingLetters,5(1976),146–148.
6.M.J.Fischer,“EfficiencyofEquivalenceAlgorithms,”inComplexityofComputerComputation
(eds.R.E.MillerandJ.W.Thatcher),PlenumPress,NewYork,1972,153–168.
7.M.L.FredmanandM.E.Saks,“TheCellProbeComplexityofDynamicDataStructures,”
ProceedingsoftheTwenty-firstAnnualSymposiumonTheoryofComputing(1989),345–354.
8.H.N.GabowandR.E.Tarjan,“ALinear-TimeAlgorithmforaSpecialCaseofDisjointSet
Union,”JournalofComputerandSystemSciences,30(1985),209–221.
9.B.A.GallerandM.J.Fischer,“AnImprovedEquivalenceAlgorithm,”Communicationsofthe
ACM,7(1964),301–303.
10.J. E. . Hopcroft t and R. M. Karp, “An Algorithm for Testing the Equivalence of Finite
Automata,” Technical Report TR-71-114, Department t of Computer r Science, Cornell
University,Ithaca,N.Y.,1971.
11.J.E.HopcroftandJ.D.Ullman,“SetMergingAlgorithms,”SIAMJournalonComputing,2
(1973),294–303.
12.D. E. . Knuth and A. . Schonhage, “The Expected d Linearity of a Simple Equivalence
Algorithm,”TheoreticalComputerScience,6(1978),281–315.
13.J.A.LaPoutre,“NewTechniquesfortheUnion-FindProblem,”ProceedingsoftheFirstAnnual
ACM–SIAMSymposiumonDiscreteAlgorithms(1990),54–63.
14.J.A.LaPoutre,“LowerBoundsfortheUnion-FindandtheSplit-FindProblemonPointer
Machines,”ProceedingsoftheTwenty-secondAnnualACMSymposiumonTheoryofComputing
(1990),34–44.
15.R. Seidel and M. Sharir, “Top-Down Analysis s of PathCompression,” SIAMJournal on
Computing,34(2005),515–525.
16.R.E.Tarjan,“EfficiencyofaGoodbutNotLinearSetUnionAlgorithm,”JournaloftheACM,
22(1975),215–225.
17.R.E.Tarjan,“AClassofAlgorithmsWhichRequireNonlinearTimetoMaintainDisjoint
Sets,”JournalofComputerandSystemSciences,18(1979),110–127.
C# PDF Convert to SVG SDK: Convert PDF to SVG files in C#.net, ASP
and WinForms applications. Support converting PDF document to SVG image within C#.NET project without quality loss. C# sample code
images from pdf to powerpoint; convert pdf to ppt online without email
378
Chapter8 TheDisjointSetsClass
18.R.E.Tarjan,“ApplicationsofPathCompressiononBalancedTrees,”JournaloftheACM,26
(1979),690–715.
19.R.E.TarjanandJ.vanLeeuwen,“Worst-CaseAnalysisofSetUnionAlgorithms,”Journalof
theACM,31(1984),245–281.
20.M.J.vanKreveldandM.H.Overmars,“Union-CopyStructuresandDynamicSegment
Trees,”JournaloftheACM,40(1993),635–652.
21.J.WestbrookandR.E.Tarjan,“AmortizedAnalysisofAlgorithmsforSetUnionwithBack-
tracking,”SIAMJournalonComputing,18(1989),1–11.
22.A.C.Yao,“OntheAverageBehaviorofSetMergingAlgorithms,”ProceedingsofEighthAnnual
ACMSymposiumontheTheoryofComputation(1976),192–195.
C H A P P T E R
9
GraphAlgorithms
Inthischapter,wediscussseveralcommonproblemsingraphtheory.Notonlyarethese
algorithmsusefulinpractice,theyarealsointerestingbecauseinmanyreal-lifeapplications
theyaretooslowunlesscarefulattentionispaidtothechoiceofdatastructures.Wewill...
Showseveralreal-lifeproblems,whichcanbeconvertedtoproblemsongraphs.
Givealgorithmstosolveseveralcommongraphproblems.
Showhowtheproperchoiceofdatastructurescandrasticallyreducetherunningtime
ofthesealgorithms.
Seeanimportanttechnique,knownasdepth-firstsearch,andshowhowitcanbeused
tosolveseveralseeminglynontrivialproblemsinlineartime.
9.1 Definitions
AgraphG=(V,E)consistsofasetofvertices,V,andasetofedges,E.Eachedgeisapair
(v,w),wherev,wV.Edgesaresometimesreferredtoasarcs.Ifthepairisordered,then
thegraphisdirected.Directedgraphsaresometimesreferredtoasdigraphs.Vertexwis
adjacenttovifandonlyif(v,w)∈E.Inanundirectedgraphwithedge(v,w),andhence
(w,v),wisadjacenttovandvisadjacenttow.Sometimesanedgehasathirdcomponent,
knownaseitheraweightoracost.
Apathinagraphisasequenceofverticesw
1
,w
2
,w
3
,...,w
N
suchthat(w
i
,w
i+1
)∈E
for1≤<N.Thelengthofsuchapathisthenumberofedgesonthepath,whichis
equaltoN−1.Weallowapathfromavertextoitself;ifthispathcontainsnoedges,then
thepathlengthis0.Thisisaconvenientwaytodefineanotherwisespecialcase.Ifthe
graphcontainsanedge(v,v)fromavertextoitself,thenthepathv,vissometimesreferred
toasaloop.Thegraphswewillconsiderwillgenerallybeloopless.Asimplepathisa
pathsuchthatallverticesaredistinct,exceptthatthefirstandlastcouldbethesame.
Acycleinadirectedgraphisapathoflengthatleast1suchthatw
1
=w
N
;thiscycle
issimpleifthepathissimple.Forundirectedgraphs,werequirethattheedgesbedistinct.
Thelogicoftheserequirementsisthatthepathu,v,uinanundirectedgraphshouldnot
beconsideredacycle,because(u,v)and(v,u)arethesameedge.Inadirectedgraph,these
aredifferentedges,soitmakessensetocallthisacycle.Adirectedgraphisacyclicifithas
nocycles.Adirectedacyclicgraphissometimesreferredtobyitsabbreviation,DAG.
379
380
Chapter9 GraphAlgorithms
Anundirectedgraphisconnectedifthereisapathfromeveryvertextoeveryother
vertex.Adirectedgraphwiththisproperty iscalledstronglyconnected.Ifadirected
graphisnotstronglyconnected,buttheunderlyinggraph(withoutdirectiontothearcs)
isconnected,thenthegraphissaidtobeweaklyconnected.Acompletegraphisagraph
inwhichthereisanedgebetweeneverypairofvertices.
Anexampleofareal-lifesituationthatcanbemodeledbyagraphistheairportsystem.
Eachairportisavertex,andtwoverticesareconnectedbyanedgeifthereisanonstop
flightfromtheairportsthatarerepresentedbythevertices.Theedgecouldhaveaweight,
representingthetime,distance,orcostoftheflight.Itisreasonabletoassumethatsuch
agraphisdirected,sinceitmighttakelongerorcostmore(dependingonlocaltaxes,
forexample)toflyindifferentdirections.Wewouldprobablyliketomakesurethatthe
airportsystemisstronglyconnected,sothatitisalwayspossibletoflyfromanyairportto
anyotherairport.Wemightalsoliketoquicklydeterminethebestflightbetweenanytwo
airports.“Best”couldmeanthepathwiththefewestnumberofedgesorcouldbetaken
withrespecttoone,orall,oftheweightmeasures.
Trafficflowcanbemodeledbyagraph.Eachstreetintersectionrepresentsavertex,
andeachstreetisanedge.Theedgecostscouldrepresent,amongotherthings,aspeed
limitoracapacity(numberoflanes).Wecouldthenaskfortheshortestrouteorusethis
informationtofindthemostlikelylocationforbottlenecks.
Intheremainderofthischapter,wewillseeseveralmoreapplicationsofgraphs.Many
ofthesegraphscanbequitelarge,soitisimportantthatthealgorithmsweusebeefficient.
9.1.1 RepresentationofGraphs
Wewillconsiderdirectedgraphs(undirectedgraphsaresimilarlyrepresented).
Suppose,fornow,thatwecannumberthevertices,startingat1.Thegraphshownin
Figure9.1represents7verticesand12edges.
4
7
5
2
3
6
1
Figure9.1 Adirectedgraph
9.1 Definitions
381
Onesimplewaytorepresentagraphistouseatwo-dimensionalarray.Thisisknownas
anadjacencymatrixrepresentation.Foreachedge(u,v),wesetA[u][v]to
true
;otherwise
theentryinthearrayis
false
.Iftheedgehasaweightassociatedwithit,thenwecanset
A[u][v]equaltotheweightanduseeitheraverylargeoraverysmallweightasasentinel
toindicatenonexistentedges.Forinstance,ifwewerelookingforthecheapestairplane
route,wecouldrepresentnonexistentflightswithacostof∞.Ifwewerelooking,for
somestrangereason,forthemostexpensiveairplaneroute,wecoulduse−∞(orperhaps
0)torepresentnonexistentedges.
Althoughthishasthemeritofextremesimplicity,thespacerequirementis(|V|
2
),
whichcanbeprohibitiveifthegraphdoesnothaveverymanyedges.Anadjacencymatrix
isanappropriaterepresentationifthegraphisdense:|E|=(|V|
2
).Inmostoftheappli-
cationsthatweshallsee,thisisnottrue.Forinstance,supposethegraphrepresentsa
streetmap.AssumeaManhattan-likeorientation,wherealmostallthestreetsruneither
north–southoreast–west.Therefore,anyintersectionisattachedtoroughlyfourstreets,
soifthegraphisdirectedandallstreetsaretwo-way,then|E|≈4|V|.Ifthereare3,000
intersections,thenwehavea3,000-vertexgraphwith12,000edgeentries,whichwould
requireanarrayofsize9,000,000.Mostoftheseentrieswouldcontainzero.Thisisintu-
itivelybad,becausewewantourdatastructurestorepresentthedatathatareactuallythere
andnotthedatathatarenotpresent.
Ifthegraphisnotdense,inotherwords,ifthegraphissparse,abettersolutionis
anadjacencylistrepresentation.Foreachvertex,wekeepalistofalladjacentvertices.
ThespacerequirementisthenO(|E|+|V|),whichislinearinthesizeofthegraph.
1
The
abstractrepresentationshouldbeclearfromFigure9.2.Iftheedgeshaveweights,then
thisadditionalinformationisalsostoredintheadjacencylists.
Adjacencylistsarethestandardwaytorepresentgraphs.Undirectedgraphscanbe
similarlyrepresented;eachedge(u,v)appearsintwolists,sothespaceusageessentially
doubles.Acommonrequirementingraphalgorithmsistofindallverticesadjacenttosome
givenvertexv,andthiscanbedone,intimeproportionaltothenumberofsuchvertices
found,byasimplescandowntheappropriateadjacencylist.
Thereareseveralalternativesformaintainingtheadjacencylists.First,observethatthe
liststhemselvescanbemaintainedineither
vector
sor
list
s.However,forsparsegraphs,
whenusing
vector
s,theprogrammermayneedtoinitializeeach
vector
withasmaller
capacitythanthedefault;otherwise,therecouldbesignificantwastedspace.
Becauseitisimportanttobeabletoquicklyobtainthelistofadjacentverticesforany
vertex,thetwobasicoptionsaretouseamapinwhichthekeysareverticesandthevalues
areadjacencylists,ortomaintaineachadjacencylistasadatamemberofa
Vertex
class.
Thefirstoptionisarguablysimpler,butthesecondoptioncanbefaster,becauseitavoids
repeatedlookupsinthemap.
Inthesecondscenario,ifthevertexisa
string
(forinstance,anairportname,orthe
nameofastreetintersection),thenamapcanbeusedinwhichthekeyisthevertexname
andthevalueisa
Vertex
(typicallyapointertoa
Vertex
),andeach
Vertex
objectkeepsa
listof(pointerstothe)adjacentverticesandperhapsalsotheoriginal
string
name.
1
Whenwespeakoflinear-timegraphalgorithms,O(|E|+|V|)istherunningtimewerequire.
Documents you may be interested
Documents you may be interested