382
Chapter9 GraphAlgorithms
2, 4, 3
4, 5
6
6, 7, 3
4, 7
(empty)
6
1
2
3
4
5
6
7
Figure9.2 Anadjacencylistrepresentationofagraph
Inmostofthechapter,wepresentthegraphalgorithmsusingpseudocode.Wewilldo
thistosavespaceand,ofcourse,tomakethepresentationofthealgorithmsmuchclearer.
AttheendofSection9.3,weprovideaworkingC
++
implementationofaroutinethat
makesunderlyinguseofashortest-pathalgorithmtoobtainitsanswers.
9.2 TopologicalSort
Atopologicalsortisanorderingofverticesinadirectedacyclicgraph,suchthatifthereis
apathfromv
i
tov
j
,thenv
j
appearsafterv
i
intheordering.ThegraphinFigure9.3repre-
sentsthecourseprerequisitestructureatastateuniversityinMiami.Adirectededge(v,w)
indicatesthatcoursevmustbecompletedbeforecoursewmaybeattempted.Atopologi-
calorderingofthesecoursesisanycoursesequencethatdoesnotviolatetheprerequisite
requirement.
Itisclearthatatopologicalorderingisnotpossibleifthegraphhasacycle,since
fortwoverticesvandwonthecycle,vprecedeswandwprecedesv.Furthermore,the
orderingisnotnecessarilyunique;anylegalorderingwilldo.InthegraphinFigure9.4,
v
1
,v
2
,v
5
,v
4
,v
3
,v
7
,v
6
andv
1
,v
2
,v
5
,v
4
,v
7
,v
3
,v
6
arebothtopologicalorderings.
Asimplealgorithmtofindatopologicalorderingisfirsttofindanyvertexwithno
incomingedges.Wecanthenprintthisvertex,andremoveit,alongwithitsedges,from
thegraph.Thenweapplythissamestrategytotherestofthegraph.
Toformalizethis,wedefinetheindegreeofavertexvasthenumberofedges(u,v).
Wecomputetheindegreesofallverticesinthegraph.Assumingthattheindegreeforeach
Adding pdf to powerpoint slide - 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
converter pdf to powerpoint; convert pdf into powerpoint online
Adding pdf to powerpoint slide - 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
export pdf into powerpoint; convert pdf to editable ppt
9.2 TopologicalSort
383
MAC3311
COP3210
CAP3700
COP3337
COP3400
MAD2104
COP4555
CDA4101
COP3530
MAD3512
CDA4400
MAD3305
COP4225
COP4610
CIS4610
COP4540
COP5621
Figure9.3 Anacyclicgraphrepresentingcourseprerequisitestructure
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figure9.4 Anacyclicgraph
vertexisstored,andthatthegraphisreadintoanadjacencylist,wecanthenapplythe
algorithminFigure9.5togenerateatopologicalordering.
Thefunction
findNewVertexOfIndegreeZero
scansthearrayofverticeslookingforaver-
texwithindegree0thathasnotalreadybeenassignedatopologicalnumber.Itreturns
NOT_A_VERTEX
ifnosuchvertexexists;thisindicatesthatthegraphhasacycle.
Because
findNewVertexOfIndegreeZero
isasimplesequentialscanofthearrayofver-
tices,eachcalltoittakesO(|V|)time.Sincethereare|V|suchcalls,therunningtimeof
thealgorithmisO(|V|2).
Bypayingmorecarefulattentiontothedatastructures,itispossibletodobetter.The
causeofthepoorrunningtimeisthesequentialscanthroughthearrayofvertices.Ifthe
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
insert or delete any certain PowerPoint slide without affecting on C#.NET PPT image adding library. powerful & profession imaging controls, PDF document, tiff
change pdf to powerpoint; how to convert pdf to ppt for
VB.NET PowerPoint: Edit PowerPoint Slide; Insert, Add or Delete
To view C# code for adding, inserting or To view more VB.NET PowerPoint slide processing functions powerful & profession imaging controls, PDF document, image
copying image from pdf to powerpoint; convert pdf slides to powerpoint online
384
Chapter9 GraphAlgorithms
void Graph::topsort( )
{
for( int counter = 0; counter < < NUM_VERTICES; ; counter++ + )
{
Vertex v v = = findNewVertexOfIndegreeZero( );
if( v v == NOT_A_VERTEX )
throw CycleFoundException{ };
v.topNum = = counter;
for each h Vertex x w adjacent to v
w.indegree--;
}
}
Figure9.5 Simpletopologicalsortpseudocode
graphissparse,wewouldexpectthatonlyafewverticeshavetheirindegreesupdateddur-
ingeachiteration.However,inthesearchforavertexofindegree0,welookat(potentially)
allthevertices,eventhoughonlyafewhavechanged.
Wecanremovethisinefficiencybykeepingallthe(unassigned)verticesofindegree0
inaspecialbox.The
findNewVertexOfIndegreeZero
functionthenreturns(andremoves)any
vertexinthebox.Whenwedecrementtheindegreesoftheadjacentvertices,wecheck
eachvertexandplaceitintheboxifitsindegreefallsto0.
Toimplementthebox,wecanuseeitherastackoraqueue;wewilluseaqueue.First,
theindegreeiscomputedforeveryvertex.Thenallverticesofindegree0areplacedonan
initiallyemptyqueue.Whilethequeueisnotempty,avertexvisremoved,andallvertices
adjacenttovhavetheirindegreesdecremented.Avertexisputonthequeueassoonas
itsindegreefallsto0.Thetopologicalorderingthenistheorderinwhichthevertices
dequeue.Figure9.6showsthestatusaftereachphase.
IndegreeBeforeDequeue#
Vertex
1
2
3
4
5
6
7
v
1
0
0
0
0
0
0
0
v
2
1
0
0
0
0
0
0
v
3
2
1
1
1
0
0
0
v
4
3
2
1
0
0
0
0
v
5
1
1
0
0
0
0
0
v
6
3
3
3
3
2
1
0
v
7
2
2
2
1
0
0
0
Enqueue
v
1
v
2
v
5
v
4
v
3
,v
7
v
6
Dequeue
v
1
v
2
v
5
v
4
v
3
v
7
v
6
Figure9.6 ResultofapplyingtopologicalsorttothegraphinFigure9.4
VB.NET PowerPoint: VB Code to Draw and Create Annotation on PPT
PDF, TIFF, MS Word and Excel). Most of end users would like to install and use Microsoft PowerPoint software and create PPT slide annotation through adding a
how to convert pdf into powerpoint on; converting pdf to powerpoint slides
C# PowerPoint - How to Process PowerPoint
Use the provided easy to call and write APIs programmed in C# class to develop user-defined PowerPoint slide adding and inserting projects.
how to convert pdf into powerpoint slides; how to convert pdf into powerpoint
9.2 TopologicalSort
385
void Graph::topsort( )
{
Queue<Vertex> q;
int counter = 0;
q.makeEmpty( );
for each Vertex x v
if( v.indegree == = 0 0 )
q.enqueue( v v );
while( !q.isEmpty( ( ) ) )
{
Vertex v v = = q.dequeue( );
v.topNum = = ++counter; ; // / Assign n next number
for each Vertex x w adjacent to v
if( --w.indegree == 0 0 )
q.enqueue( w );
}
if( counter != NUM_VERTICES )
throw CycleFoundException{ };
}
Figure9.7 Pseudocodetoperformtopologicalsort
ApseudocodeimplementationofthisalgorithmisgiveninFigure9.7.Asbefore,we
willassumethatthegraphisalreadyreadintoanadjacencylistandthattheindegrees
arecomputedandstoredwiththevertices.Wealsoassumeeachvertexhasanameddata
member,
topNum
,inwhichtoplaceitstopologicalnumbering.
ThetimetoperformthisalgorithmisO(|E|+|V|)ifadjacencylistsareused.This
is apparentwhen onerealizes that thebody ofthe
for
loopisexecuted at mostonce
peredge.Computingtheindegreescanbedonewiththefollowingcode;thissamelogic
showsthatthecost ofthiscomputationisO(|E|+|V|),eventhoughtherearenested
loops.
for each h Vertex v
v.indegree = = 0;
for each h Vertex v
for each Vertex w adjacent to o v
w.indegree++;
Thequeueoperationsaredoneatmostoncepervertex,andtheotherinitializationsteps,
including thecomputationofindegrees,alsotaketimeproportionaltothe sizeof the
graph.
VB.NET PowerPoint: VB Codes to Create Linear and 2D Barcodes on
PowerPoint PDF 417 barcode library is a mature and This PowerPoint ISSN barcode adding control is compatible ITF-14 barcode on any PowerPoint document slide
convert pdf to ppt; export pdf to powerpoint
VB.NET PowerPoint: Read, Edit and Process PPTX File
SDK into VB.NET class application by adding several compact well, like reading Excel in VB.NET, Reading PDF in VB Independent from Microsoft PowerPoint Product.
convert pdf file to ppt online; convert pdf file to powerpoint presentation
386
Chapter9 GraphAlgorithms
9.3 Shortest-PathAlgorithms
In this section n we e examine various shortest-path problems. The input t is a a weighted
graph:Associated with eachedge(v
i
,v
j
)isacostc
i,j
totraversetheedge.Thecost of
apathv
1
v
2
...v
N
is
N−1
i=1
c
i,i+1
.Thisisreferredtoastheweightedpath length.The
unweightedpathlengthismerelythenumberofedgesonthepath,namely,N−1.
Single-SourceShortest-PathProblem
Givenasinputaweightedgraph,G= (V,E),andadistinguishedvertex,s,findthe
shortestweightedpathfromstoeveryothervertexinG.
Forexample,inthegraphinFigure9.8,theshortestweightedpathfromv
1
tov
6
hasa
costof6andgoesfromv
1
tov
4
tov
7
tov
6
.Theshortestunweightedpathbetweenthese
verticesis2.Generally,whenitisnotspecifiedwhetherwearereferringtoaweightedor
anunweightedpath,thepathisweightedifthegraphis.Noticealsothatinthisgraph
thereisnopathfromv
6
tov
1
.
Thegraphin thepreceding examplehas noedgesofnegative cost.Thegraphin
Figure9.9showstheproblemsthatnegativeedgescancause.Thepathfromv
5
tov
4
has
6
2
4
1
3
10
2
4
8
5
1
2
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figure9.8 AdirectedgraphG
6
2
4
1
3
–10
1
2
6
2
1
5
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figure9.9 Agraphwithanegative-costcycle
C# PowerPoint: C# Guide to Add, Insert and Delete PPT Slide(s)
offer this C#.NET PowerPoint slide adding, inserting and guide for each PowerPoint slide processing operation & profession imaging controls, PDF document, tiff
pdf to ppt converter; pdf to powerpoint slide
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
easily VB.NET PPT image adding and inserting clip art or screenshot to PowerPoint document slide at powerful & profession imaging controls, PDF document, image
embed pdf into powerpoint; drag and drop pdf into powerpoint
9.3 Shortest-PathAlgorithms
387
cost1,butashorterpathexistsbyfollowingtheloopv
5
,v
4
,v
2
,v
5
,v
4
,whichhascost−5.
Thispathisstillnottheshortest,becausewecouldstayinthelooparbitrarilylong.Thus,
theshortestpathbetweenthesetwopointsisundefined.Similarly,theshortestpathfrom
v
1
tov
6
isundefined,becausewecangetintothesameloop.Thisloopisknownasa
negative-costcycle;whenoneispresentinthegraph,theshortestpathsarenotdefined.
Negative-costedgesarenotnecessarilybad,asthecyclesare,buttheirpresenceseemsto
maketheproblemharder.Forconvenience,intheabsenceofanegative-costcycle,the
shortestpathfromstosiszero.
Therearemanyexampleswherewemightwanttosolvetheshortest-pathproblem.
Iftheverticesrepresentcomputers;theedgesrepresentalinkbetweencomputers;and
thecostsrepresentcommunicationcosts(phonebillperamegabyteofdata),delaycosts
(numberofsecondsrequiredtotransmitamegabyte),oracombinationoftheseandother
factors,thenwecanusetheshortest-pathalgorithmtofind thecheapestwaytosend
electronicnewsfromonecomputertoasetofothercomputers.
Wecanmodelairplaneorothermass transitroutesby graphsanduseashortest-
pathalgorithmtocomputethebestroutebetweentwopoints.Inthisandmanypractical
applications,wemightwanttofindtheshortestpathfromonevertex,s,toonlyoneother
vertex,t.Currentlytherearenoalgorithmsinwhichfindingthepathfromstoonevertex
isanyfaster(bymorethanaconstantfactor)thanfindingthepathfromstoallvertices.
Wewillexaminealgorithmstosolvefourversionsofthisproblem.First,wewillcon-
sidertheunweightedshortest-pathproblemandshowhowtosolveitinO(|E|+|V|).Next,
wewillshowhowtosolvetheweightedshortest-pathproblemifweassumethatthereare
nonegativeedges.TherunningtimeforthisalgorithmisO(|E|log|V|)whenimplemented
withreasonabledatastructures.
Ifthegraphhasnegativeedges,wewillprovideasimplesolution,whichunfortunately
hasapoortimeboundofO(|E|·|V|).Finally,wewillsolvetheweightedproblemforthe
specialcaseofacyclicgraphsinlineartime.
9.3.1 UnweightedShortestPaths
Figure9.10showsanunweightedgraph,G.Usingsomevertex,s,whichisaninputparam-
eter,wewouldliketofind theshortestpathfromstoallothervertices.Weareonly
interestedinthenumberofedgescontainedonthepath,sotherearenoweightsonthe
edges.Thisisclearlyaspecialcaseoftheweightedshortest-pathproblem,sincewecould
assignalledgesaweightof1.
Fornow,supposeweareinterestedonlyinthelengthoftheshortestpaths,notinthe
actualpathsthemselves.Keepingtrackoftheactualpathswillturnouttobeamatterof
simplebookkeeping.
Supposewechoosestobev
3
.Immediately,wecantellthattheshortestpathfrom
stov
3
isthenapathoflength0.Wecanmarkthisinformation,obtainingthegraphin
Figure9.11.
Nowwecanstartlookingforallverticesthatareadistance1awayfroms.Thesecan
befoundbylookingattheverticesthatareadjacenttos.Ifwedothis,weseethatv
1
and
v
6
areoneedgefroms.ThisisshowninFigure9.12.
Wecannowfindverticeswhoseshortestpathfromsisexactly2,byfindingallthe
verticesadjacenttov
1
andv
6
(theverticesatdistance1),whoseshortestpathsarenot
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
functions, like VB.NET PPT slide adding/removing, PPT read this VB.NET PowerPoint slide processing tutorial & profession imaging controls, PDF document, image
convert pdf pages to powerpoint slides; add pdf to powerpoint slide
VB.NET PowerPoint: PPTX to SVG Conversion; Render PPT to Vector
into VB.NET project by adding project reference PowerPoint files that end with .pptx file suffix can powerful & profession imaging controls, PDF document, tiff
image from pdf to powerpoint; pdf page to powerpoint
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figure9.10 AnunweighteddirectedgraphG
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0
Figure9.11 Graphaftermarkingthestartnodeasreachableinzeroedges
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0
1
1
Figure9.12 Graphafterfindingallverticeswhosepathlengthfromsis1
9.3 Shortest-PathAlgorithms
389
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0
1
1
2
2
Figure9.13 Graphafterfindingallverticeswhoseshortestpathis2
alreadyknown.Thissearchtellsusthattheshortestpathtov
2
andv
4
is2.Figure9.13
showstheprogressthathasbeenmadesofar.
Finallywecanfind,byexaminingverticesadjacenttotherecentlyevaluatedv
2
andv
4
,
thatv
5
andv
7
haveashortestpathofthreeedges.Allverticeshavenowbeencalculated,
andsoFigure9.14showsthefinalresultofthealgorithm.
Thisstrategyforsearchingagraphisknownasbreadth-firstsearch.Itoperatesby
processingverticesinlayers:Theverticesclosesttothestartareevaluatedfirst,andthe
mostdistantverticesareevaluatedlast.Thisismuchthesameasalevel-ordertraversalfor
trees.
Given this strategy,we must translateit into code. . Figure 9.15 shows the initial
configurationofthetablethatouralgorithmwillusetokeeptrackofitsprogress.
Foreachvertex,wewillkeeptrackofthreepiecesofinformation.First,wewillkeep
itsdistancefromsintheentryd
v
.Initiallyallverticesareunreachableexceptfors,whose
pathlengthis0.Theentryinp
v
isthebookkeepingvariable,whichwillallowustoprint
theactualpaths.Theentryknownissetto
true
afteravertex isprocessed.Initially,all
entriesarenotknown,includingthestartvertex.Whenavertexismarkedknown,wehave
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0
1
1
2
2
3
3
Figure9.14 Finalshortestpaths
390
Chapter9 GraphAlgorithms
v
known
d
v
p
v
v
1
F
0
v
2
F
0
v
3
F
0
0
v
4
F
0
v
5
F
0
v
6
F
0
v
7
F
0
Figure9.15 Initialconfigurationoftableusedinunweightedshortest-pathcomputation
aguaranteethatnocheaperpathwilleverbefound,andsoprocessingforthatvertexis
essentiallycomplete.
ThebasicalgorithmcanbedescribedinFigure9.16.ThealgorithminFigure9.16
mimicsthediagramsbydeclaringasknowntheverticesatdistance= 0,then= 1,
thend=2,andsoon,andsettingalltheadjacentverticeswthatstillhaved
w
=∞toa
distanced
w
=d+1.
void Graph::unweighted( Vertex s s )
{
for each Vertex v
{
v.dist = = INFINITY;
v.known = false;
}
s.dist = = 0;
for( int currDist t = = 0; currDist t < < NUM_VERTICES; ; currDist++ )
for each h Vertex x v
if( !v.known n && v.dist t == currDist t )
{
v.known = true;
for each h Vertex x w adjacent to v
if( w.dist == INFINITY )
{
w.dist = = currDist t + + 1;
w.path = = v;
}
}
}
Figure9.16 Pseudocodeforunweightedshortest-pathalgorithm
9.3 Shortest-PathAlgorithms
391
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
Figure9.17 Abadcaseforunweightedshortest-pathalgorithmusingFigure9.16
Bytracingbackthroughthep
v
variable,theactualpathcanbeprinted.Wewillsee
howwhenwediscusstheweightedcase.
TherunningtimeofthealgorithmisO(|V|
2
),becauseofthedoublynested
for
loops.
Anobviousinefficiencyisthattheoutsideloopcontinuesuntil
NUM_VERTICES-1
,evenifall
theverticesbecomeknownmuchearlier.Althoughanextratestcouldbemadetoavoid
this,itdoesnotaffecttheworst-caserunningtime,ascanbeseenbygeneralizingwhat
happenswhentheinputisthegraphinFigure9.17withstartvertexv
9
.
Wecanremovetheinefficiencyinmuchthesamewayaswasdonefortopologicalsort.
Atanypointintime,thereareonlytwotypesofunknownverticesthathaved
v
=∞.Some
haved
v
=
currDist
,andtheresthaved
v
=
currDist + 1
.Becauseofthisextrastructure,it
isverywastefultosearchthroughtheentiretabletofindapropervertex.
Averysimplebutabstractsolutionistokeeptwoboxes.Box#1willhavetheunknown
verticeswithd
v
=
currDist
,andbox#2willhaved
v
=
currDist + + 1
.Thetesttofindan
appropriatevertexvcanbereplacedbyfindinganyvertexinbox#1.Afterupdatingw
(insidetheinnermost
if
block),wecanaddwtobox#2.Aftertheoutermost
for
loop
terminates,box#1isempty,andbox#2canbetransferredtobox#1forthenextpassof
the
for
loop.
Wecanrefinethisideaevenfurtherbyusingjustonequeue.Atthestartofthepass,
thequeuecontainsonlyverticesofdistance
currDist
.Whenweaddadjacentverticesof
distance
currDist + + 1
,sincetheyenqueueattherear,weareguaranteedthattheywillnot
beprocesseduntilafteralltheverticesofdistance
currDist
havebeenprocessed.Afterthe
lastvertexatdistance
currDist
dequeuesandisprocessed,thequeueonlycontainsvertices
ofdistance
currDist + 1
,sothisprocessperpetuates.Wemerelyneedtobegintheprocess
byplacingthestartnodeonthequeuebyitself.
TherefinedalgorithmisshowninFigure9.18.Inthepseudocode,wehaveassumed
thatthestartvertex,s,ispassedasaparameter.Also,itispossiblethatthequeuemight
emptyprematurely,ifsomeverticesareunreachablefromthestartnode.Inthiscase,a
distanceof
INFINITY
willbereportedforthesenodes,whichisperfectlyreasonable.Finally,
the
known
datamemberisnotused;onceavertexisprocesseditcanneverenterthequeue
again,sothefactthatitneednotbereprocessedisimplicitlymarked.Thus,the
known
data
membercanbediscarded.Figure9.19showshowthevaluesonthegraphwehavebeen
usingarechangedduringthealgorithm(itincludesthechangesthatwouldoccurto
known
ifwehadkeptit).
Usingthesameanalysisaswasperformedfortopologicalsort,weseethattherunning
timeisO(|E|+|V|),aslongasadjacencylistsareused.
9.3.2 Dijkstra’sAlgorithm
Ifthegraphisweighted,theproblem(apparently)becomesharder,butwecanstillusethe
ideasfromtheunweightedcase.
Documents you may be interested
Documents you may be interested