第06章图Graph

1、graphs1chapter 6: graphsorddfwsfolax802174318431233337graphs2outline and readingwgraphs (6.1)wdata structures for graphs (6.2)wgraph traversal (6.3)wdirected graph (6.4)graphs36.1 graphwa graph is a pair (v, e), wherenv is a set of nodes, called verticesne is a collection of pairs of vertices, calle

2、d edgesnvertices and edges are positions and store elementswexample:na vertex represents an airport and stores the three-letter airport codenan edge represents a flight route between two airports and stores the mileage of the routeordpvdmiadfwsfolaxlgahnl8498021387174318431099112012333372555142graph

3、s4edge typeswdirected edgenordered pair of vertices (u,v)nfirst vertex u is the originnsecond vertex v is the destinationne.g., a flightwundirected edgenunordered pair of vertices (u,v)ne.g., a flight routewdirected graphnall the edges are directedne.g., flight networkwundirected graphnall the edges

4、 are undirectedne.g., route networkordpvdflightaa 1206ordpvd849milesgraphs5johndavidpcslab1bcslab1aapplicationswelectronic circuitsnprinted circuit boardnintegrated circuitwtransportation networksnhighway networknflight networkwcomputer networksnlocal area networkninternetnwebwdatabase

5、snentity-relationship diagramgraphs6terminologywend vertices (or endpoints) of an edgenu and v are the endpoints of awedges incident on a vertexna, d, and b are incident on vwadjacent verticesnu and v are adjacentwdegree of a vertexnx has degree 5 wparallel edgesnh and i are parallel edgeswself-loop

6、nj is a self-loopxuvwzyacbedfghijgraphs7p1terminology (cont.)wpathnsequence of alternating vertices and edges nbegins with a vertexnends with a vertexneach edge is preceded and followed by its endpointswsimple pathnpath such that all its vertices and edges are distinctwexamplesnp1=(v,b,x,h,z) is a s

7、imple pathnp2=(u,c,w,e,x,g,y,f,w,d,v) is a path that is not simplexuvwzyacbedfghp2graphs8terminology (cont.)wcyclencircular sequence of alternating vertices and edges neach edge is preceded and followed by its endpointswsimple cyclencycle such that all its vertices and edges are distinctwexamplesnc1

8、=(v,b,x,g,y,f,w,c,u,a,) is a simple cyclenc2=(u,c,w,e,x,g,y,f,w,d,v,a,) is a cycle that is not simplec1xuvwzyacbedfghc2graphs9propertiesnotation nnumber of vertices mnumber of edgesdeg(v)degree of vertex vproperty 1s sv deg(v) = 2mproof: each edge is counted twiceproperty 2in an undirected graph wit

9、h no self-loops and no multiple edges m n (n - - 1)/ /2proof: each vertex has degree at most (n - - 1)examplenn = = 4nm = = 6ndeg(v) = 3graphs10subgraphswa subgraph s of a graph g is a graph such that nthe vertices of s are a subset of the vertices of gnthe edges of s are a subset of the edges of gw

10、a spanning subgraph of g is a subgraph that contains all the vertices of gsubgraphspanning subgraphgraphs11connectivitywa graph is connected if there is a path between every pair of verticeswa connected component of a graph g is a maximal connected subgraph of gconnected graphnon connected graph wit

11、h two connected componentsgraphs12trees and forestswa (free) tree is an undirected graph t such thatnt is connectednt has no cyclesthis definition of tree is different from the one of a rooted treewa forest is an undirected graph without cycleswthe connected components of a forest are treestreefores

12、tgraphs13spanning trees and forestswa spanning tree of a connected graph is a spanning subgraph that is a treewa spanning tree is not unique unless the graph is a treewspanning trees have applications to the design of communication networkswa spanning forest of a graph is a spanning subgraph that is

13、 a forestgraphspanning treegraphs14main methods of the graph adtwvertices and edgesnare positionsnstore elementswaccessor methodsnavertex()nincidentedges(v)nendvertices(e)nisdirected(e)norigin(e)ndestination(e)nopposite(v, e)nareadjacent(v, w)wupdate methodsninsertvertex(o)ninsertedge(v, w, o)ninser

14、tdirectededge(v, w, o)nremovevertex(v)nremoveedge(e)wgeneric methodsnnumvertices()nnumedges()nvertices()nedges()graphs156.2 data structure for graphsgraphs16edge list structurewvertex objectnelementnreference to position in vertex sequencewedge objectnelementnorigin vertex objectndestination vertex

15、objectnreference to position in edge sequencewvertex sequencensequence of vertex objectswedge sequencensequence of edge objectsvuwacbazduvwzbcdgraphs17adjacency list structurewedge list structurewincidence sequence for each vertexnsequence of references to edge objects of incident edgeswaugmented ed

16、ge objectsnreferences to associated positions in incidence sequences of end verticesuvwabauvwbgraphs18adjacency matrix structurewedge list structurewaugmented vertex objectsninteger key (index) associated with vertexw2d adjacency arraynreference to edge object for adjacent verticesnnull for non nona

17、djacent verticeswthe “old fashioned” version just has 0 for no edge and 1 for edgeuvwab012012auvw012bgraphs19asymptotic performancew n vertices, m edgesw no parallel edgesw no self-loopsw bounds are “big-oh”edgelistadjacencylistadjacency matrixspacen + mn + mn2incidentedges(v)mdeg(v)nareadjacent (v,

18、 w)mmin(deg(v), deg(w)1insertvertex(o)11n2insertedge(v, w, o)111graphs206.3 graph traversalgraphs216.3.1 depth-first searchwdepth-first search (dfs) is a general technique for traversing a graphwa dfs traversal of a graph g nvisits all the vertices and edges of gndetermines whether g is connectednco

19、mputes the connected components of gncomputes a spanning forest of gwdfs on a graph with n vertices and m edges takes o(n + m ) timewdfs can be further extended to solve other graph problemsnfind and report a path between two given verticesnfind a cycle in the graphwdepth-first search is to graphs w

20、hat euler tour is to binary treesgraphs22dfs algorithmwthe algorithm uses a mechanism for setting and getting “labels” of vertices and edgesalgorithm dfs(g, v)input graph g and a start vertex v of g output labeling of the edges of g in the connected component of v as discovery edges and back edgesse

21、tlabel(v, visited)for all e g.incidentedges(v)if getlabel(e) = unexploredw g.opposite(v,e)if getlabel(w) = unexploredsetlabel(e, discovery)dfs(g, w)elsesetlabel(e, back)algorithm dfs(g)input graph goutput labeling of the edges of g as discovery edges andback edgesfor all u g.vertices()setlabel(u, un

22、explored)for all e g.edges()setlabel(e, unexplored)for all v g.vertices()if getlabel(v) = unexploreddfs(g, v)graphs23exampledbacedbacedbacediscovery edgeback edgeavisited vertexaunexplored vertexunexplored edgegraphs24example (cont.)dbacedbacedbacedbacegraphs25dfs and maze traversal wthe dfs algorit

23、hm is similar to a classic strategy for exploring a mazenwe mark each intersection, corner and dead end (vertex) visitednwe mark each corridor (edge ) traversednwe keep track of the path back to the entrance (start vertex) by means of a rope (recursion stack)graphs26properties of dfsproperty 1dfs(g,

24、 v) visits all the vertices and edges in the connected component of vproperty 2the discovery edges labeled by dfs(g, v) form a spanning tree of the connected component of vdbacegraphs27analysis of dfswsetting/getting a vertex/edge label takes o(1) timeweach vertex is labeled twice nonce as unexplore

25、dnonce as visitedweach edge is labeled twicenonce as unexplorednonce as discovery or backwmethod incidentedges is called once for each vertexwdfs runs in o(n + m) time provided the graph is represented by the adjacency list structurenrecall that s sv deg(v) = 2mgraphs28path findingwwe can specialize

26、 the dfs algorithm to find a path between two given vertices u and z using the template method patternwwe call dfs(g, u) with u as the start vertexwwe use a stack s to keep track of the path between the start vertex and the current vertexwas soon as destination vertex z is encountered, we return the

27、 path as the contents of the stack algorithm pathdfs(g, v, z)setlabel(v, visited)s.push(v)if v = zreturn s.elements()for all e g.incidentedges(v)if getlabel(e) = unexploredw opposite(v, e)if getlabel(w) = unexplored setlabel(e, discovery)s.push(e)pathdfs(g, w, z)s.pop() e gets popped else setlabel(e

28、, back)s.pop() v gets popped graphs29cycle findingwwe can specialize the dfs algorithm to find a simple cycle using the template method patternwwe use a stack s to keep track of the path between the start vertex and the current vertexwas soon as a back edge (v, w) is encountered, we return the cycle

29、 as the portion of the stack from the top to vertex walgorithm cycledfs(g, v, z)setlabel(v, visited)s.push(v)for all e g.incidentedges(v)if getlabel(e) = unexploredw opposite(v,e)s.push(e)if getlabel(w) = unexplored setlabel(e, discovery)pathdfs(g, w, z)s.pop()elsec new empty stackrepeato s.pop()c.p

30、ush(o)until o = wreturn c.elements()s.pop()graphs306.3.2 biconnectivityseapvdmiasnaordfcographs31separation edges and verticeswdefinitionsnlet g be a connected graphna separation edge of g is an edge whose removal disconnects g na separation vertex of g is a vertex whose removal disconnects g wappli

31、cationsnseparation edges and vertices represent single points of failure in a network and are critical to the operation of the networkwexamplendfw, lga and lax are separation verticesn(dfw,lax) is a separation edgeordpvdmiadfwsfolaxlgahnlgraphs32biconnected graphwequivalent definitions of a biconnec

32、ted graph gngraph g has no separation edges and no separation verticesnfor any two vertices u and v of g, there are two disjoint simple paths between u and v (i.e., two simple paths between u and v that share no other vertices or edges)nfor any two vertices u and v of g, there is a simple cycle cont

33、aining u and v wexampleordpvdmiadfwsfolaxlgahnlgraphs33biconnected componentswbiconnected component of a graph gna maximal biconnected subgraph of g, orna subgraph consisting of a separation edge of g and its end verticeswinteraction of biconnected componentsnan edge belongs to exactly one biconnect

34、ed componentna nonseparation vertex belongs to exactly one biconnected componentna separation vertex belongs to two or more biconnected componentswexample of a graph with four biconnected componentsordpvdmiadfwsfolaxlgahnlrdugraphs34equivalence classeswgiven a set s, a relation r on s is a set of or

35、dered pairs of elements of s, i.e., r is a subset of s swan equivalence relation r on s satisfies the following propertiesreflexive: (x,x) rsymmetric: (x,y) r (y,x) rtransitive: (x,y) r (y,z) r (x,z) rwan equivalence relation r on s induces a partition of the elements of s into equivalence classeswe

36、xample (connectivity relation among the vertices of a graph):nlet v be the set of vertices of a graph gndefine the relationc = (v,w) v v such that g has a path from v to w nrelation c is an equivalence relationnthe equivalence classes of relation c are the vertices in each connected component of gra

37、ph ggraphs35link relationwedges e and f of connected graph g are linked ifne = f, orng has a simple cycle containing e and ftheorem:the link relation on the edges of a graph is an equivalence relationproof sketch:nthe reflexive and symmetric properties follow from the definitionnfor the transitive p

38、roperty, consider two simple cycles sharing an edgeabgcjdefiequivalence classes of linked edges:a b, c, d, e, f g, i, jabgcjdefigraphs36link componentswthe link components of a connected graph g are the equivalence classes of edges with respect to the link relationwa biconnected component of g is th

39、e subgraph of g induced by an equivalence class of linked edgeswa separation edge is a single-element equivalence class of linked edgeswa separation vertex has incident edges in at least two distinct equivalence classes of linked edgeordpvdmiadfwsfolaxlgahnlrdugraphs37auxiliary graphwauxiliary graph

40、 b for a connected graph gnassociated with a dfs traversal of gnthe vertices of b are the edges of gnfor each back edge e of g, b has edges (e,f1), (e,f2) , , (e,fk),where f1, f2, , fk are the discovery edges of g that form a simple cycle with enits connected components correspond to the the link co

41、mponents of gabgcjdefiauxiliary graph bdfs on graph gadbcehijfhgigraphs38auxiliary graph (cont.)win the worst case, the number of edges of the auxiliary graph is proportional to nmauxiliary graph bdfs on graph ggraphs39proxy graphalgorithm proxygraph(g)input connected graph goutput proxy graph f for

42、 gf empty graphdfs(g, s) s is any vertex of gfor all discovery edges e of gf.insertvertex(e)setlabel(e, unlinked)for all vertices v of g in dfs visit orderfor all back edges e = (u,v) f.insertvertex(e)repeatf discovery edge with dest. uf.insertedge(e,f,) if f getlabel(f) = unlinkedsetlabel(f, linked

43、)u origin of edge felseu v ends the loop until u = vreturn fabgcjdefiproxy graph fdfs on graph gadbcehijfhgigraphs40proxy graph (cont.)wproxy graph f for a connected graph g nspanning forest of the auxiliary graph bnhas m vertices and o(m) edgesncan be constructed in o(n + m) timenits connected comp

44、onents (trees) correspond to the the link components of gwgiven a graph g with n vertices and m edges, we can compute the following in o(n + m) timenthe biconnected components of gnthe separation vertices of gnthe separation edges of gabgcjdefiproxy graph fdfs on graph gadbcehijfhgigraphs416.3.3 bre

45、adth-first searchcbaedl0l1fl2graphs42breadth-first searchwbreadth-first search (bfs) is a general technique for traversing a graphwa bfs traversal of a graph g nvisits all the vertices and edges of gndetermines whether g is connectedncomputes the connected components of gncomputes a spanning forest

46、of gwbfs on a graph with n vertices and m edges takes o(n + m ) timewbfs can be further extended to solve other graph problemsnfind and report a path with the minimum number of edges between two given vertices nfind a simple cycle, if there is onegraphs43bfs algorithmwthe algorithm uses a mechanism

47、for setting and getting “labels” of vertices and edgesalgorithm bfs(g, s)l0 new empty sequencel0.insertlast(s)setlabel(s, visited)i 0 while li.isempty()li +1 new empty sequence for all v li.elements() for all e g.incidentedges(v) if getlabel(e) = unexploredw opposite(v,e)if getlabel(w) = unexploreds

48、etlabel(e, discovery)setlabel(w, visited)li +1.insertlast(w)elsesetlabel(e, cross)i i +1algorithm bfs(g)input graph goutput labeling of the edges and partition of the vertices of g for all u g.vertices()setlabel(u, unexplored)for all e g.edges()setlabel(e, unexplored)for all v g.vertices()if getlabe

49、l(v) = unexploredbfs(g, v)graphs44examplecbaeddiscovery edgecross edgeavisited vertexaunexplored vertexunexplored edgel0l1fcbaedl0l1fcbaedl0l1fgraphs45example (cont.)cbaedl0l1fcbaedl0l1fl2cbaedl0l1fl2cbaedl0l1fl2graphs46example (cont.)cbaedl0l1fl2cbaedl0l1fl2cbaedl0l1fl2graphs47propertiesnotationgs:

50、 connected component of sproperty 1bfs(g, s) visits all the vertices and edges of gs property 2the discovery edges labeled by bfs(g, s) form a spanning tree ts of gsproperty 3for each vertex v in linthe path of ts from s to v has i edges nevery path from s to v in gs has at least i edgescbaedl0l1fl2

51、cbaedfgraphs48analysiswsetting/getting a vertex/edge label takes o(1) timeweach vertex is labeled twice nonce as unexplorednonce as visitedweach edge is labeled twicenonce as unexplorednonce as discovery or crossweach vertex is inserted once into a sequence li wmethod incidentedges is called once fo

52、r each vertexwbfs runs in o(n + m) time provided the graph is represented by the adjacency list structurenrecall that s sv deg(v) = 2mgraphs49applicationswusing the template method pattern, we can specialize the bfs traversal of a graph g to solve the following problems in o(n + m) timencompute the

53、connected components of gncompute a spanning forest of gnfind a simple cycle in g, or report that g is a forestngiven two vertices of g, find a path in g between them with the minimum number of edges, or report that no such path existsgraphs50dfs vs. bfscbaedl0l1fl2cbaedfdfsbfsapplicationsdfsbfsspan

54、ning forest, connected components, paths, cycles shortest paths biconnected components graphs51dfs vs. bfs (cont.)back edge (v,w)nw is an ancestor of v in the tree of discovery edgescross edge (v,w)nw is in the same level as v or in the next level in the tree of discovery edgescbaedl0l1fl2cbaedfdfsb

55、fsgraphs526.4 directed graphsjfkbosmiaordlaxdfwsfographs53outline and reading (6.4) wreachability (6.4.1)ndirected dfsnstrong connectivitywtransitive closure (6.4.2)nthe floyd-warshall algorithmwdirected acyclic graphs (dags) (6.4.4)ntopological sortinggraphs54digraphswa digraph is a graph whose edg

56、es are all directednshort for “directed graph”wapplicationsnone-way streetsnflightsntask schedulingacebdgraphs55digraph propertieswa graph g=(v,e) such thatneach edge goes in one direction:wedge (a,b) goes from a to b, but not b to a.wif g is simple, m n(n-1).wif we keep in-edges and out-edges in se

57、parate adjacency lists, we can perform listing of of the sets of in-edges and out-edges in time proportional to their size.acebdgraphs56digraph applicationwscheduling: edge (a,b) means task a must be completed before b can be startedthe good lifeics141ics131ics121ics53ics52ics51ics23ics22ics21ics161

58、ics151ics171graphs57directed dfswwe can specialize the traversal algorithms (dfs and bfs) to digraphs by traversing edges only along their directionwin the directed dfs algorithm, we have four types of edgesndiscovery edgesnback edgesnforward edgesncross edgeswa directed dfs starting at a vertex s d

59、etermines the vertices reachable from sacebdgraphs58reachabilitywdfs tree rooted at v: vertices reachable from v via directed pathsacebdfacedacebdfgraphs59strong connectivityweach vertex can reach all other verticesadcbefggraphs60wpick a vertex v in g.wperform a dfs from v in g.nif theres a w not vi

60、sited, print “no”.wlet g be g with edges reversed.wperform a dfs from v in g.nif theres a w not visited, print “no”.nelse, print “yes”.wrunning time: o(n+m).strong connectivity algorithmg:g:adcbefgadcbefggraphs61wmaximal subgraphs such that each vertex can reach all other vertices in the subgraphwca