数据结构（双语）48课时版15-16-Graph Algorithms

DataStructure

数据结构计算机与信息技术系袁莹Email:yuanying@2021年6月8日9GraphAlgorithms9.1Definitions9.2TopologicalSort9.3Shorted-PathAlgorithms9.5MinimumSpanningTree参考中文书第6章：6.1/6.2.1/6.2.2/6.4/6.5.1/6.6CHAPTER9GRAPHALGORITHMSterminology：graph图vertex顶点edge边directed有向的adjacent邻接weight/cost权值path路径length长度loop环cycle圈acyclic无圈的connected连通的stronglyconnected强连通的weaklyconnected弱连通的completegraph完全图CHAPTER9GRAPHALGORITHMS§1DefinitionsG(V,E)whereG::=graph,V=V(G)::=finitenonemptysetofvertices,andE=E(G)::=finitesetofedges.Undirectedgraph:(vi,vj)=(vj,vi)::=thesameedge.Directedgraph(digraph):<

vi,vj>::=<vj,vi>vivjtailheadRestrictions:

(1)Selfloopisillegal.(2)Multigraphisnotconsidered01012Completegraph:agraphthathasthemaximumnumberofedges02130213vivjviandvjareadjacent;edge(vi,vj)isincidenton

viandvj

vivjviisadjacent

to

vj

;vjisadjacent

from

vi

;

edge<vi,vj>isincidenton

viandvj

SubgraphG’G::=V(G’)V(G)&&E(G’)E(G)Path(G)fromvp

tovq

::={vp,vi1,vi2,,vin,vq}suchthat(vp,vi1),(vi1,vi2),,(vin,vq)or<vp,vi1>,,<vin,vq>belongtoE(G)Lengthofapath::=numberofedgesonthepathSimplepath

::=vi1,vi2,,vinaredistinctCycle

::=simplepathwithvp

=vq

vi

andvj

inanundirectedGare

connected

ifthereisapathfromvi

tovj

(andhencethereisalsoapathfromvj

tovi)AnundirectedgraphGis

connected

ifeverypairofdistinctvi

andvj

areconnected§1Definitions§1Definitions(Connected)ComponentofanundirectedG

::=themaximal

connected

subgraphAtree::=agraphthatisconnectedandacyclicStronglyconnecteddirectedgraphG::=foreverypairofvi

andvj

inV(G),thereexistdirectedpathsfromvi

tovj

andfromvj

tovi.Ifthegraphisconnectedwithoutdirectiontotheedges,thenitissaidtobeweaklyconnectedStronglyconnectedcomponent::=themaximalsubgraphthatisstronglyconnectedDegree(v)

::=numberofedgesincidenttov.ForadirectedG,wehavein-degreeandout-degree.Forexample:vin-degree(v)=3;out-degree(v)=1;degree(v)=4GivenGwithnverticesandeedges,thenADAG::=adirectedacyclicgraph§1DefinitionsRepresentationofGraphsAdjacencyMatrixadj_mat[n][n]isdefinedforG(V,E)withnvertices,n1:Note:IfGisundirected,thenadj_mat[][]issymmetric.Thuswecansavespacebystoringonlyhalfofthematrix.Iknowwhatyou’reabouttosay:thisrepresentationwastesspaceifthegraphhasalotofverticesbutveryfewedges,right?Heyyoubegintoknowme!Right.Anditwastestimeaswell.IfwearetofindoutwhetherornotGisconnected,we’llhavetoexaminealledges.InthiscaseTandSarebothO(n2)Thetrickistostorethematrixasa1-Darray:adj_mat[n(n+1)/2]={a11,a21,a22,...,an1,...,ann}Theindexforaij

is(i(i1)/2+j).§1DefinitionsAdjacencyListsReplaceeachrowbyalinkedlist〖Example〗0121graph[0]0graph[1]2graph[2]Note:Theorderofnodesineachlistdoesnotmatter.ForundirectedG:S=V+2EFordirectedG:S=V+EExercise7654321AdjacencyMatrixAdjacencyListsSpace12345671234567§2TopologicalSort〖Example〗CoursesneededforacomputersciencedegreeatahypotheticaluniversityHowshallweconvertthislistintoagraph?§2TopologicalSortAOVNetwork::=digraphGinwhichV(G)representsactivities(e.g.thecourses)andE(G)representsprecedencerelations(e.g.

meansthatC1isaprerequisitecourseofC3).C1C3iisapredecessorofj::=thereisapathfromitojiisanimmediatepredecessorofj::=<i,j>E(G)Thenjiscalledasuccessor(immediatesuccessor)ofiFeasibleAOVnetworkmustbeaDAG(directedacyclicgraph).（AOV:ActivityOnVertexnetwork）§2TopologicalSort【Definition】Atopologicalorderisalinearorderingoftheverticesofagraphsuchthat,foranytwovertices,i,j,ifiisapredecessorofjinthenetworktheniprecedesjinthelinearordering.〖Example〗Onepossiblesuggestiononcoursescheduleforacomputersciencedegreecouldbe:§2TopologicalSortNote:Thetopologicalordersmaynotbeuniqueforanetwork.Forexample,thereareseveralways(topologicalorders)tomeetthedegreerequirementsincomputerscience.GoalTestanAOVforfeasibility,andgenerateatopologicalorderifpossible.voidTopsort(GraphG){intCounter;VertexV,W;

for(Counter=0;Counter<NumVertex;Counter++){

V=FindNewVertexOfInDegreeZero();

if(V==NotAVertex){ Error(“Graphhasacycle”);break;} TopNum[V]=Counter;/*oroutputV*/

for(eachWadjacenttoV) Indegree[W]––;}}/*O(|V|)*/

T=O(|V|2)V1V2V4V3V6V5AOVNetworktopologicalorderV6V1V4V3V2V5不唯一！Exercise：AOVNetwork->topologicalorder§2TopologicalSort

Improvement:Keepalltheunassignedverticesofdegree0inaspecialbox(queueorstack).v1v2v6v7v3v4v5voidTopsort(GraphG){QueueQ;

intCounter=0;VertexV,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);

for(eachvertexV)

if(Indegree[V]==0)Enqueue(V,Q);

while(!IsEmpty(Q)){

V=Dequeue(Q); TopNum[V]=++Counter;/*assignnext*/

for(eachWadjacenttoV)

if(––Indegree[W]==0)Enqueue(W,Q);}/*end-while*/

if(Counter!=NumVertex) Error(“Graphhasacycle”);DisposeQueue(Q);/*freememory*/}0v1Indegree1v22v33v41v53v62v7v10v21210v50v41v60v320v710T=O(|V|+|E|)MistakesinFig9.4onp.287§3ShortestPathAlgorithmsGivenadigraphG=(V,E),andacostfunctionc(e)fore

E(G).ThelengthofapathPfromsourcetodestinationis(alsocalledweightedpathlength).1.Single-SourceShortest-PathProblemGivenasinputaweightedgraph,G=(V,E),andadistinguishedvertex,s,findtheshortestweightedpathfromstoeveryothervertexinG.v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v524213–10258461Negative-costcycleNote:Ifthereisnonegative-costcycle,theshortestpathfromstosisdefinedtobezero.§3ShortestPathAlgorithmsUnweightedShortestPathsv1v2v6v7v3v4v500:

v31:v1andv6112:v2andv4223:v5andv733SketchoftheideaBreadth-firstsearchImplementationTable[i].Dist::=distancefromstovi/*initializedtobeexceptfors*/Table[i].Known::=1ifviischecked;or0ifnotTable[i].Path::=fortrackingthepath/*initializedtobe0*/§3ShortestPathAlgorithmsvoidUnweighted(TableT){intCurrDist;VertexV,W;

for(CurrDist=0;CurrDist<NumVertex;CurrDist++){

for(eachvertexV)

if(!T[V].Known&&T[V].Dist==CurrDist){ T[V].Known=true;

for(eachWadjacenttoV)

if(T[W].Dist==Infinity){ T[W].Dist=CurrDist+1; T[W].Path=V; }/*end-ifDist==Infinity*/ }/*end-if!Known&&Dist==CurrDist*/}/*end-forCurrDist*/}Theworstcase:v1v2v6v7v3v4v5v9v8

T=O(|V|2)IfVisunknownyethasDist<Infinity,thenDistiseitherCurrDistorCurrDist+1.§3ShortestPathAlgorithmsImprovementvoidUnweighted(TableT){/*TisinitializedwiththesourcevertexSgiven*/QueueQ;VertexV,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueuethesourcevertex*/

while(!IsEmpty(Q)){V=Dequeue(Q);T[V].Known=true;/*notreallynecessary*/

for(eachWadjacenttoV)

if(T[W].Dist==Infinity){ T[W].Dist=T[V].Dist+1; T[W].Path=V; Enqueue(W,Q); }/*end-ifDist==Infinity*/}/*end-while*/

DisposeQueue(Q);/*freememory*/}v1v2v6v7v3v4v50v1Dist

Pathv20v3v4v5v6v70000000v3v71v3v11v3v61122v1v222v1v433v2v533v4T=O(|V|+|E|)§3ShortestPathAlgorithms

Dijkstra’sAlgorithm(forweightedshortestpaths)LetS={sandvi’swhoseshortestpathshavebeenfound}Foranyu

S,definedistance[u]=minimallengthofpath{s

(vi

S)u}.Ifthepathsaregeneratedinnon-decreasingorder,thentheshortestpathmustgothroughONLY

vi

S;Why?Ifitisnottrue,thentheremustbeavertexwonthispaththatisnotinS.Then...uischosensothatdistance[u]=min{wS|distance[w]}(Ifuisnotunique,thenwemayselectanyofthem);/*GreedyMethod*/ifdistance[u1]<distance[u2]andweaddu1intoS,thendistance[u2]maychange.Ifso,ashorterpathfromstou2mustgothroughu1anddistance’[u2]=distance[u1]+length(<u1,u2>).§3ShortestPathAlgorithmsvoidDijkstra(TableT){/*TisinitializedbyFigure9.30onp.301*/VertexV,W;for(;;){V=smallestunknowndistancevertex;if(V==NotAVertex) break;T[V].Known=true;

for(eachWadjacenttoV)

if(!T[W].Known)

if(T[V].Dist+Cvw<T[W].Dist){ Decrease(T[W].Distto T[V].Dist+Cvw); T[W].Path=V; }/*end-ifupdateW*/}/*end-for(;;)*/}v1v2v6v7v3v4v524213102584610v1DistPathv2v3v4v5v6v700000002v11v13v43v49v45v48v36v7/*notworkforedgewithnegativecost*/PleasereadFigure9.31onp.302forprintingthepath./*O(|V|)*/

Dijkstra’sAlgorithm(forweightedshortestpaths)§3ShortestPathAlgorithmsImplementation1V=smallestunknowndistancevertex;/*simplyscanthetable–O(|V|)*/T=O(|V|2+|E|)GoodifthegraphisdenseImplementation2V=smallestunknowndistancevertex;/*keepdistancesinapriorityqueueandcallDeleteMin–O(log|V|)*/Decrease(T[W].DisttoT[V].Dist+Cvw);/*Method1:DecreaseKey–O(log|V|)*/T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)/*Method2:insertWwithupdatedDistintothepriorityqueue*//*MustkeepdoingDeleteMinuntilanunknownvertexemerges*/GoodifthegraphissparseT=O(|E|log|V|)butrequires|E|DeleteMinwith|E|spaceOtherimprovements:Pairingheap(Ch.12)andFibonacciheap(Ch.11)Homework:p.3379.5FindtheshortestpathsGFEDCBA152327126731Exercise:p.3379.5FindtheshortestpathsfromAtoallothervertices:(1)UnweightedShortestPaths(2)WeightedShortestPathsvknowndvpvABCDEFG§3ShortestPathAlgorithmsGraphswithNegativeEdgeCostsHeyIhaveagoodidea:whydon’twesimplyaddaconstanttoeachedgeandthusremovenegativeedges?Toosimple,andnaïve…Trythisoneout:

13422–221voidWeightedNegative(TableT){/*TisinitializedbyFigure9.30onp.303*/QueueQ;VertexV,W;

Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueuethesourcevertex*/

while(!IsEmpty(Q)){V=Dequeue(Q);for(eachWadjacenttoV)

if(T[V].Dist+Cvw<T[W].Dist){ T[W].Dist=T[V].Dist+Cvw; T[W].Path=V; if(WisnotalreadyinQ) Enqueue(W,Q); }/*end-ifupdate*/}/*end-while*/

DisposeQueue(Q);/*freememory*/}/*negative-costcyclewillcauseindefiniteloop*//*nolongeronceperedge*//*eachvertexcandequeueatmost|V|times*/T=O(|V||E|)§4NetworkFlowProblems〖Example〗Considerthefollowingnetworkofpipes:sdcbat33322214sourcesinkNote:Totalcomingin(v)

Totalgoingout(v)wherev{s,t}Determinethemaximumamountofflowthatcanpassfromstot.§4NetworkFlowProblems1.ASimpleAlgorithmsdcbat33322214GsdcbatFlowGfsdcbatResidualGrStep1:Findanypaths

tinGr

;augmentingpathStep2:TaketheminimumedgeonthispathastheamountofflowandaddtoGf

;Step3:UpdateGr

andremovethe0flowedges;Step4:If(thereisapaths

tinGr)GotoStep1;ElseEnd.§4NetworkFlowProblemssdcbat33322214GItissimpleindeed.ButIbetthatyouwillpointoutsomeproblemshere…Youareright!WhatifIpickupthepaths

adtfirst?Uh-oh…Seemswecannotbegreedyatthispoint.§4NetworkFlowProblems2.ASolution–allowthealgorithmtoundoitsdecisionsForeachedge(v,w)withflowfv,winGf

,addanedge(w,v)withflowfv,winGr

.sdcbatFlowGfsdcbat33322214GsdcbatResidualGr333222143333313222222213221〖Proposition〗

Iftheedgecapabilitiesarerationalnumbers,thisalgorithmalwaysterminatewithamaximumflow.Note:ThealgorithmworksforGwithcyclesaswell.§4NetworkFlowProblems3.Analysis(Ifthecapacitiesareallintegers)Anaugmentingpathcanbefoundbyanunweightedshortestpathalgorithm.T=O()wherefisthemaximumflow.f·|E|stab10000001000000100000010000001Alwayschoosetheaugmentingpaththatallowsthelargestincreaseinflow./*modifyDijkstra’salgorithm*/T=Taugmentation*Tfindapath=O(|E|logcapmax

)*O(|E|log|V|)=O(|E|2log|V|)ifcapmaxisasmallinteger.§4NetworkFlowProblemsAlwayschoosetheaugmentingpaththathastheleastnumberofedges.T=Taugmentation*Tfindapath=O(|E|)*O(|E|·|V|)=O(|E|2|V|)/*unweightedshortestpathalgorithm*/Note:

Ifeveryv{s,t}haseitherasingleincomingedgeofcapacity1orasingleoutgoingedgeofcapacity1,thentimeboundisreducedtoO(|E||V|1/2).Themin-costflowproblemistofind,amongallmaximumflows,theoneflowofminimumcostprovidedthateachedgehasacostperunitofflow.Homework:p.3419.11Atestcase.§5MinimumSpanningTree【Definition】AspanningtreeofagraphGisatreewhichconsistsofV(G)andasubsetofE(G)〖Example〗AcompletegraphandthreeofitsspanningtreesNote:

Theminimumspanningtreeisatreesinceitisacyclic--thenumberofedgesis|V|–1.Itisminimumforthetotalcostofedgesisminimized.Itisspanningbecauseitcoverseveryvertex.AminimumspanningtreeexistsiffGisconnected.Addinganon-treeedgetoaspanningtree,weobtainacycle.§5MinimumSpanningTreeGreedyMethodMakethebestdecisionforeachstage,underthefollowingconstrains:(1)wemustuseonlyedgeswithinthegraph;(2)wemustuseexactly|V|-1edges;(3)wemaynotuseedgesthatwouldproduceacycle.1.Prim’sAlgorithm–growatree/*verysimilartoDijkstra’salgorithm*/v1v2v6v7v3v4v52421310758461§5MinimumSpanningTree2.Kruskal’sAlgorithm–maintainaforestvoidKruskal(GraphG){T={};

while(Tcontainslessthan|V|-1edges&&Eisnotempty){choosealeastcostedge(v,w)fromE;delete(v,w)fromE;

if((v,w)doesnotcreateacycleinT) add(v,w)toT;

else

discard(v,w);}

if(Tcontainsfewerthan|V|-1edges)Error(“Nospanningtree”);}/*DeleteMin*//*Union/Find*/AmoredetailedpseudocodeisgivenbyFigure9.58onp.321T=O(|E|log|E|)§6ApplicationsofDepth-FirstSearch/*ageneralizationofpreordertraversal*/voidDFS(VertexV)/*thisisonlyatemplate*/{visited[V]=true;/*markthisvertextoavoidcycles*/

for(eachWadjacenttoV)

if(!visited[W]) DFS(W);}/*T=O(|E|+|V|)aslongasadjacencylistsareused*/0123456DFS(0)1.UndirectedGraphsvoidListComponents(GraphG){for(eachVinG)

if(!visited[V]){ DFS(V);printf(“\n“);}}78014652378§6ApplicationsofDepth-FirstSearch2.BiconnectivityArticulationpointBiconnectedgraph

visanarticulationpointifG’=DeleteVertex(G,v)hasatleast2connectedcomponents.GisabiconnectedgraphifGisconnectedandhasnoarticulationpoints.Abiconnectedcomponentisamaximalbiconnectedsubgraph.〖Example〗0123487569Connectedgraph011234358775679BiconnectedcomponentsNote:Noedgescanbesharedbytwoormorebiconnectedcomponents.HenceE(G)ispartitionedbythebiconnectedcomponentsofG.§6ApplicationsofDepth-FirstSe