T&RTeamofAlgorithmDesignCollegeofComputerScienceandEngineering,CQUAlgorithmAnalysis&Design

IntroductiontoAlgorithmChapter22:

ElementaryGraphAlgorithms

outlinesBasicnotionsofgraphsStandardgraph-searchingalgorithmsDefinitionsGraphG=(V,E)V=setofverticesE=setofedges(VV)|E|=O(|V|2)TypesofGraphsUndirected:edge(u,v)=(v,u);

forallv,(v,v)E(Noselfloops.)Directed:(u,v)isedgefromutov,denotedasuv.Selfloopsareallowed.Weighted:eachedgehasanassociatedweight,givenbyaweightfunctionw:ER.Definitions–continue-If(u,v)E,thenvertexvisadjacenttovertexu.Adjacencyrelationshipis:SymmetricifGisundirected.NotnecessarilysoifGisdirected.IfGisconnected:Thereisapathbetweeneverypairofvertices.|E|

|V|–1.Furthermore,if|E|

=|V|–1,thenGisatree.RepresentationofGraphsTwostandardways.AdjacencyLists.AdjacencyMatrix.adcb

abcdb

a

d

d

c

c

a

b

a

c

adcb1234123410111210103110141010AdjacencyListsConsistsofanarrayAdjof|V|lists.Onelistpervertex.Foru

V,Adj[u]={allverticesadjacenttou}.adcb

abcdb

c

d

d

c

adcb

abcdb

a

d

d

c

c

a

b

a

c

Ifweighted,storeweightsalsoinadjacencylists.StorageRequirementFordirectedgraphs:Sumoflengthsofalladj.listsis

out-degree(v)=|E|

vV

Totalstorage:

(|V|+|E|)Forundirectedgraphs:Sumoflengthsofalladj.listsis

degree(v)=2|E|

vV

Totalstorage:

(|V|+|E|)NumberofedgesleavingvNumberofedgesincidentonv.AdjacencyMatrix|V||V|matrixA.Numberverticesfrom1to|V|Aisthengivenby:adcb1234123410111200103000140000adcb1234123410111210103110141010A=ATforundirectedgraphs.SpaceandTimeSpace:

(|V|2).Notmemoryefficientforlargegraphs.Time:

tolistallverticesadjacenttou:(|V|).Time:

todetermineif(u,v)

E:(1).Canstoreweightsforweightedgraph.

Graph-SearchingAlgorithms

Standard

AlgorithmsSearchingagraph:Systematicallyfollowtheedgesofagraph

tovisittheverticesofthegraphdiscoveringthestructureofagraph.Standardgraph-searchingalgorithms.Breadth-firstSearch(BFS).Depth-firstSearch(DFS).Breadth-FirstSearchInput:

-GraphG=(V,E),eitherdirectedorundirected,

-sourcevertexs

V.Output:

forallv

Vd[v]=lengthofshortestpathfromstov

(d[v]=ifvisnotreachablefroms).[v]=uif(u,v)

islastedgeonshortestpathsv.uisv’spredecessor.breadth-firsttree

=atreewithrootsthatcontainsallreachablevertices.DefinitionsonBSFPathbetweenverticesuandv:

vertices(v1,v2,…,vk)suchthat

u=v1

andv=vk,(vi,vi+1)E,forall1ik-1.Lengthofthepath:Numberofedgesinthepath.Pathissimpleifnovertexisrepeated.PrincipleofBreadth-FirstSearchExpandsthefrontierbetweendiscoveredandundiscoveredverticesuniformly

acrossthebreadthofthefrontier.Avertexis“discovered”thefirsttimeitisencounteredduringthesearch.Avertexis“finished”ifallverticesadjacenttoithavebeendiscovered.BFSforShortestPathsFinishedDiscoveredS111S222222S33333Colorstheverticestokeeptrackofprogress.UndiscoveredSBFS(G,s)1. foreachvertexuinV[G]–{s}2 do

color[u]white3 d[u]

4 [u]nil5 color[s]gray6 d[s]07 [s]nil8 Q9 enqueue(Q,s)10 whileQ11 doudequeue(Q)12 foreachvinAdj[u]13 do

ifcolor[v]=white14 thencolor[v]gray15 d[v]d[u]+116 [v]u17 enqueue(Q,v)18 color[u]blackwhite:undiscoveredgray:discoveredblack:finishedQ:aqueueofdiscoveredverticescolor[v]:colorofvd[v]:distancefromstov[u]:predecessorofvExample(BFS)0rstuvwxyQ:s0frontierExample(BFS)0rstuvwxyQ:s0frontierExample(BFS)101rstuvwxyQ:wr11Example(BFS)10122rstuvwxyQ:rtx122Example(BFS)101222rstuvwxyQ:txv222Example(BFS)1012232rstuvwxyQ:xvu223Example(BFS)10123232rstuvwxyQ:vuy233Example(BFS)10123232rstuvwxyQ:uy33Example(BFS)10123232rstuvwxyQ:y3Example(BFS)10123232rstuvwxyQ:

Example(BFS)10123232rstuvwxyBFTreeBreadth-FirstTreePredecessorsub-graph

ofG=(V,E)withsourcesisG=(V,E)whereV={vV:[v]NIL}+{s}E={([v],v)E:vV-{s}}Gisabreadth-firsttreeif:

VconsistsoftheverticesreachablefromsforallvV,thereisauniquesimplepathfromstovinG

thepathisalsoashortestpathfromstovinG.TheedgesinEarecalledtreeedges.

|E|=|V|-1.AnalysisofBFSInitializationtakesO(|V|).TraversalLoopEachvertexisenqueuedanddequeuedatmostonce,sothetotaltimeforqueuingisO(|V|).Theadjacencylistofeachvertexisscannedatmostonce.Thesumoflengthsofalladjacencylistsis(|E|).TotalrunningtimeofBFSisO(|V|+|E|)CorrectnessofBFS(seeDijkstralater)Exercises22.2-222.2-5ShortTestinClasssComputetheshortestdistancesofeachvertexfromthesourcevertexs,andgivetheBSFtreeofthegraphbelow.Depth-FirstSearch(DFS)Exploreedgesoutofthemostrecentlydiscoveredvertexv.Whenalledgesofvhavebeenexplored,backtracktoitspredecessortoexploreotheredges“Searchasdeepaspossiblefirst.”Continueuntilallverticesarediscovered.Depth-FirstSearchInput:

G=(V,E),directedorundirected.Nosourcevertexgiven!Output:

2timestamps

oneachvertex.d[v]=discoverytime(vturnsfromwhitetogray)f[v]=finishingtime(vturnsfromgraytoblack)[v]:predecessorofv=u,suchthatvwasdiscoveredduringthescanofu’sadjacencylist.ProgramDFS(G)1.foreachvertexuV[G]2.docolor[u]white3.[u]NIL4.time

05.foreachvertexuV[G]6.doifcolor[u]=white7.thenDFS-Visit(u)Usesaglobaltimestamptime.DFS-Visit(u)color[u]GRAYuhasbeendiscoveredtimetime+1

d[u]

time

foreachvAdj[u]

do

if

color[v]=WHITE

then

[v]

uDFS-Visit(v)

color[u]BLACKBlackenu;itisfinished.

f[u]

timetime+1DFS:KindsofedgesDFSintroducesanimportantdistinctionamongedgesintheoriginalgraph:Treeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/uvwxyzTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/2/uvwxyzTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/3/2/uvwxyzTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/3/2/uvwxyzTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/3/2/uvwxyzBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/53/2/uvwxyzBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/53/62/uvwxyzBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/53/62/7uvwxyzBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/4/53/62/7uvwxyzBFTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/62/7uvwxyzBFTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/62/79/uvwxyzBFTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/62/79/uvwxyzBFCTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/610/2/79/uvwxyzBFCTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/610/2/79/uvwxyzBFCBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/610/112/79/uvwxyzBFCBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesExample(DFS)1/84/53/610/112/79/12uvwxyzBFCBTreeedge:encounternew(white)vertexBackedge:fromdescendenttoancestorForwardedge:fromancestortodescendentCrossedge:betweenatreeorsubtreesClassificationofEdgesTreeedge:

inthedepth-firstforest,byexploring(u,v).Backedge:

(u,v),whereuisadescendantofv(inthedepth-firsttree).(includeself-loop)Forwardedge:

(u,v),wherevisadescendantofu,butnotatreeedge.Crossedge:

anyotheredge.Cangobetweenverticesinsamedepth-firsttreeorindifferentdepth-firsttrees.IdentificationofEdgesEdgetypeforedge(u,v)

canbeidentifiedwhenitisfirstexploredbyDFS.Identificationisbasedonthecolorofv.White–treeedge.Gray–backedge.Black–forwardorcrossedge.IdentificationofEdgesTheorem:InDFSofanundirectedgraph,wegetonlytreeandbackedges.Noforwardorcrossedges.Proofbycontradiction:Assumethere’saforwardedgeButF?edgemustactuallybeabackedge(why?)sourceF?IdentificationofEdgesTheorem:InDFSofanundirectedgraph,wegetonlytreeandbackedges.Noforwardorcrossedges.sourceC?Proofbycontradiction:Assumethere’sacrossedgeButC?edgecannotbecross!Soinfactthepictureiswrong…bothlowertreeedgescannotinfactbetreeedgesDepth-FirstTreesPredecessorsubgraphisslightlydifferentfromthatofBFS.ThepredecessorsubgraphofDFSG=(V,E)

E={([v],v)

:vV

and

[v]NIL}.

Gformsadepth-firstforestcomposedofseveraldepth-firsttrees.Econsistsoftreeedges.Definition:Forest:AnacyclicgraphGthatmaybedisconnected.AnalysisofDFSDFS(G)1.foreachvertexuV[G]2.docolor[u]white3.[u]NIL4.time

05.foreachvertexuV[G]6.doifcolor[u]=white7.thenDFS-Visit(u)Usesaglobaltimestamptime.DFS-Visit(u)color[u]GRAY

uhasbeendiscoveredtimetime+1

d[u]

time

foreachvAdj[u]

do

if

color[v]=WHITE

then

[v]

uDFS-Visit(v)

color[u]BLACK

Blackenu;itisfinished.

f[u]

timetime+1AnalysisofDFSLoopsonlines1-2&5-7take(|V|)time,excludingtimetoexecuteDFS-Visit.DFS-VisitiscalledonceforeachwhitevertexvVwhenit’spaintedgraythefirsttime.Lines3-6ofDFS-Visitisexecuted|Adj[v]|times.ThetotalcostofexecutingDFS-VisitisvV|Adj[v]|=(|E|)

TotalrunningtimeofDFSis

(|V|+|E|).ParenthesisTheoremTheorem22.7Forallu,v,exactlyoneofthefollowingholds:1.d[u]<f[u]<d[v]<f[v]ord[v]<f[v]<d[u]<f[u]andneitherunorvisadescendantoftheother.2.d[u]<d[v]<f[v]<f[u]andvisadescendantofu.3.d[v]<d[u]<f[u]<f[v]anduisadescendantofv.Sod[u]<d[v]<f[u]<f[v]cannothappen.Likeparentheses:OK:()[]([])[()]NotOK:([)][(])Corollaryvisaproperdescendantofuifandonlyifd[u]<d[v]<f[v]<f[u].Example(ParenthesisTheorem)3/64/57/812/132/91/10yzsxwvBF14/1511/16utCCCCB(s(z(y(xx)y)(ww)z)s)(t(vv)(uu)t)White-pathTheorem

Theorem22.9visadescendantofuifandonlyifattimed[u],thereisapathu

vconsistingofonlywhitevertices.(Exceptforu,whichwasjustcoloredgray.)1/uvxyExercises22.3-222.3-322.3-8ShortTestinClass1/sComputethe(d[v]/f[v])foreachvertexvandidentifythetypeofeachedge.

TopologicalSorting

DirectedAcyclicGraphDAG–Directedgraphwithnocycles.Goodformodelingprocessesandstructuresthathaveapartialorder:a>bandb>c

a>c.(transitiveclosure)Butmayhaveaandbsuchthatneithera>bnorb>a.Canalwaysmakeatotalorder

(eithera>borb>aforalla

b)fromapartialorder.ExampleDAGofdependenciesforputtingongoalieequipment.socksshortshosepantsskateslegpadsT-shirtchestpadsweatermaskcatchgloveblockerbattinggloveCharacterizingaDAGProof::Showthatbackedgecycle.Supposethereisabackedge(u,v).Thenvisancestorofuindepth-firstforest.Therefore,thereisapathv

u,sov

u

visacycle.Lemma22.11AdirectedgraphGisacycliciffaDFSofGyieldsnobackedges.vuTTTBCharacterizingaDAGProof(Contd.)::Showthatacycleimpliesabackedge.c

:cycleinG,v:firstvertexdiscoveredinc,(u,v):v’sprecedingedgeinc.Attimed[v],verticesofcformawhitepathvu.Why?Bywhite-paththeorem,uisadescendentofvindepth-firstforest.Therefore,(u,v)

isabackedge.vuTTTBTopologicalSortWantto“