數(shù)據(jù)結(jié)構(gòu)（雙語(yǔ)）CH28-Graph Algorithms

DataStructure

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)與信息技術(shù)系袁瑩Email:yuanying8011@163.com

2014年5月30日CHAPTER9GRAPHALGORITHMSterminology：graph圖vertex頂點(diǎn)edge邊directed有向的adjacent鄰接weight/cost權(quán)值path路徑length長(zhǎng)度loop環(huán)cycle圈acyclic無(wú)圈的connected連通的stronglyconnected強(qiáng)連通的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:agraphthathasthemaximumnumberofedges021302131/13vivjviandvjareadjacent;(vi,vj)isincidenton

viandvj

vivjviisadjacent

to

vj

;vjisadjacent

from

vi

;<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§1Definitions2/13§1Definitions(Connected)ComponentofanundirectedG

::=themaximalconnectedsubgraphAtree::=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::=adirectedacyclicgraph3/13§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).4/13§1DefinitionsAdjacencyListsReplaceeachrowbyalinkedlist〖Example〗0121graph[0]0graph[1]2graph[2]Note:Theorderofnodesineachlistdoesnotmatter.ForundirectedG:S=V+2EFordirectedG:S=V+E5/13§2TopologicalSort〖Example〗CoursesneededforacomputersciencedegreeatahypotheticaluniversityHowshallweconvertthislistintoagraph?8/13§2TopologicalSortAOVNetwork::=digraphGinwhichV(G)representsactivities(e.g.thecourses)andE(G)representsprecedencerelations(e.g.meansthatC1isaprerequisitecourseofC3).C1C3iisapredecessorofj::=thereisapathfromitoj

iisanimmediatepredecessorofj::=<i,j>E(G)Thenjiscalledasuccessor(immediatesuccessor)ofiFeasibleAOVnetworkmustbeaDAG

(directedacyclicgraph).9/13§2TopologicalSort【Definition】Atopologicalorderisalinearorderingoftheverticesofagraphsuchthat,foranytwovertices,i,j,ifiisapredecessorofjinthenetworktheniprecedesjinthelinearordering.〖Example〗

Onepossiblesuggestiononcoursescheduleforacomputersciencedegreecouldbe:10/13§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)11/13§2TopologicalSort

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

intCo