數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：chapter8 Graph

1、Software College Northeastern University1Data StructureSoftware College Northeastern University2DCBCdabegfPregalRiver柯尼斯堡柯尼斯堡7橋問題橋問題Kneiphof島島AData StructureSoftware College Northeastern University3ABCDdcabegfData StructureSoftware College Northeastern University4Data StructureSoftware College North

2、eastern University5 A graph consists of a set V of vertices, V, and a set E of edges, E. Each edge is a pair( v, w),where If the pair is ordered, then the graph is directed(有向圖). Else the graph is undirected（無向圖）. is the set of edges or arcs. Data StructureSoftware College Northeastern University6Gr

3、aph TerminologyzThere are two kinds of graphs, directed and undirected:.Data StructureSoftware College Northeastern University7 V0 V4 V3 V1 V2zAny undirected graph can be represented as a directed graph by replacing each undirected edge with two directed edges. yIn undirected graphs, the edges are p

4、lain lines which have no direction.yIn undirected graphs, you can go either way along an edge.Graph TerminologyData StructureSoftware College Northeastern University8 V0V0 V1V1 V2V2 V3V3zA directed graph (digraph) is a graph in which vertices at each edge are ordered. yIn directed graphs, the edges

5、are arrows directed from one node to another. is Graph TerminologyData StructureSoftware College Northeastern University9 V0V0 V1V1 V2V2 V3V3yIn directed graphs, you can only go from node to node following the direction of the arrows. This means that in a directed graph it is possible to reach a dea

6、d end, or to get to a node from which you cannot leave. Graph TerminologyData StructureSoftware College Northeastern University10Applications of GraphAir flight system Each vertex represents a city Each edge represents a direct flight between two cities A query on direct flights becomes a query on w

7、hether an edge exists A query on how to get to a location is “does a path exist from A to B” We can even associate costs to edges (weighted graphs), then ask “what is the cheapest path from A to B”Data StructureSoftware College Northeastern University11V0V0 V1V1 V2V2 V3V3Applications of GraphData St

8、ructureSoftware College Northeastern University12Control flow in a computer program vertex: basic blocks arc: possible transfers of flow of control V0V0 V1V1 V2V2 V3V3Applications of GraphData StructureSoftware College Northeastern University13 complete graphn(n-1)/2n(n-1)Graph TerminologyData Struc

9、tureSoftware College Northeastern University14Graph TerminologyzSometimes edges have a third component, weight or cost, the semantics of which is specific to the graph. zA graph that has values associated with its edges is called a weighted graph. The graph can be either directed or undirected. The

10、weights can represent things like: yPhysical distance between two vertices. yTime it takes to get from one vertex to another. yHow much it costs to travel from vertex to vertex. Data StructureSoftware College Northeastern University15Graph TerminologyzAn example of weighted directed graphData Struct

11、ureSoftware College Northeastern University16Let G = (V, E) be a graph with vertex set V and edge set E. A subgraph of G is a graph G = (V, E) where 1. V is a subset of V. 2. E consists of edges (v, w) in E such that both v and w are in V.Graph TerminologyData StructureSoftware College Northeastern

12、University17zThe degree of vertex v is the number of edges link to v-TD(v)。zIn directed graph, vertex degree is sum of in-degree and out-degreezIn-degree of v is the number of edges whose tail is v- ID(v)zOut-degree of v is the number of edges whose head is v- OD(v)。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1

13、V1 V2V2 V3V3Graph TerminologyData StructureSoftware College Northeastern University18Graph TerminologyIn the directed graph, there is an edge from node 2 to node 1. Therefore: The two nodes are adjacent or they are neighbors. Node 2 is a predecessor of node 1. Node 1 is a successor of node 2. The so

14、urce of the edge is node 2, and the target of the edge is node 1. 12Data StructureSoftware College Northeastern University19Graph TerminologyIn the undirected graph, there is an edge between node 1 and node 3. Therefore: z Nodes 1 and 3 are adjacent or they are neighbors. 13Data StructureSoftware Co

15、llege Northeastern University20Graph TerminologyzA path is a sequence of vertices w1, w2, w3, ., wn such that (wi,wi+1) in E for 1= i= 1 such that w1 = wn. zA simple cycle is a cycle composed of a simple path. Data StructureSoftware College Northeastern University22Graph TerminologyzIn this graph, t

16、here is a path from node 2 to node 5: 2-1-5. zThere is a path from node 1 to node 2: 1-3-4-2. zThere is also a path from node 1 back to itself: 1-3-4-2-1. zThe first two paths are acyclic paths, becuase no node is repeated.zThe last path is a cyclic path, because node 1 occurs twice. Data StructureS

17、oftware College Northeastern University23Graph TerminologyzDo you think these two graphs are the same?zYes. The layout of the graph is arbitrary - the important thing is which nodes are connected to which other nodes. Data StructureSoftware College Northeastern University24Graph TerminologyzA graph

18、is acyclic if it contains no cycles (as see earlier).zAn acyclic directed graph is often called a DAG (Directed Acyclic Graph).Data StructureSoftware College Northeastern University25Graph TerminologyzA connected graph is an undirected graph in which there is a path from every vertex to every other

19、vertex. V0V0 V4V4 V3V3 V1V1 V2V2Data StructureSoftware College Northeastern University26Graph TerminologyA strongly connected graph is a directed graph in which there is a path from every vertex to every other vertex. V0V0 V1V1 V2V2 V3V3Data StructureSoftware College Northeastern University27Graph T

20、erminologyzA weakly connected graph is a directed graph which is not strongly connected but which would be connected if the graph were converted to an undirected graph (simply ignore the directions). V0V0 V1V1 V2V2 V3V3Data StructureSoftware College Northeastern University28Graph TerminologyzA conne

21、cted component of a graph G is a maximal connected induced subgraph,that is, a connected induced subgraph that is not itself a proper subgraph of any other connected subgraph of G. V0V0 V2V2 V3V3 V1V1 V5V5 V4V4連通分量連通分量Data StructureSoftware College Northeastern University29Graph TerminologyzA strong

22、ly connected component (強(qiáng)連通分量)of a directed graph is a maximal set of vertices in which there is a path from any one vertex in the set to any other vertex in the set.zA strongly connected graph only have one strong component.強(qiáng)連通分量強(qiáng)連通分量 V0V0 V2V2 V3V3 V1V1Data StructureSoftware College Northeastern U

23、niversity30zSuppose G = (V, E) is a connected graph in which each edge (u, v) in E has a cost c(u,v) attached to it. A connected, acyclic subgraph of G which that connects all the vertices in V is a spanning tree. The cost of a spanning tree is the sum of the costs of the edges in the tree.xEvery sp

24、anning tree with n vertices contains exactly n-1 edges.xIf we add any edge to a free tree, we get a cycle.Graph TerminologyData StructureSoftware College Northeastern University31Graph Terminology V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2Data StructureSoftware Colleg

25、e Northeastern University32 directed tree: the tree with one node whose in-degree is zero. Other nodess in-degree is 1.A directed graphs spanning forest is composed of some directed trees.The trees contain all the vertices in the graph and some arcs V0V0 V1V1 V2V2 V3V3 V0V0 V1V1 V2V2 V3V3 A A B B F

26、F E E C C D D A A B B F F E E C C D DGraph TerminologyData StructureSoftware College Northeastern University33 V0V0 V4V4 V3V3 V1V1 V2V2Data StructureSoftware College Northeastern University34class Graph public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v2, int

27、 weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); Representing GraphsData StructureSoftware College Northeastern University35 V0V0 V4V4 V3V3 V1V1 V2V2

28、 V0V0 V1V1 V2V2 V3V3Representing GraphsData StructureSoftware College Northeastern University36 therwise, ),(r , , .o oo oi if f01AEjiEjijiEdgeData StructureSoftware College Northeastern University37Data StructureSoftware College Northeastern University380 1 1 00 0 0 00 0 0 110 0 0 V0V0 V4V4 V3V3 V1

29、V1 V2V2 V0 V1 V2 V3 Data StructureSoftware College Northeastern University39 ),( , ),( .jijiEjiEjijijiWjiEdge=! ,!0=A對(duì)對(duì)角角線線但但是是否否則則或或且且如如Data StructureSoftware College Northeastern University40 const int MaxNumEdges = 50;const int MaxNumVertices = 10;template class Graph private: SeqList VerticesLis

30、t (MaxNumVertices); DistType EdgeMaxNumVerticesMaxNumVertices; int CurrentEdges; int FindVertex ( SeqList & L; const NameType &vertex ) return L.Find (vertex); Data StructureSoftware College Northeastern University41 int GetVertexPos ( Const NameType &vertex ) return FindVertex (Vertices

31、List, vertex ); public: Graph ( int sz = MaxNumVertices ); int GraphEmpty ( )const return VerticesList.IsEmpty ( ); int GraphFull( ) const return VerticesList.IsFull( ) | CurrentEdges =MaxNumEdges; int NumberOfVertices ( ) return VerticesList.last +1; int NumberOfEdges ( ) return CurrentEdges; Data

32、StructureSoftware College Northeastern University42 NameType GetValue ( int i ) return i = 0 & i = VerticesList.last ? VerticesList.datai : NULL; DistType GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); void InsertVertex ( NameType & vert

33、ex ); void InsertEdge ( int v1, int v2, DistType weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 );Data StructureSoftware College Northeastern University43const int MaxDist = 0 xFFFF；template Graph : Graph( int sz) /構(gòu)造函數(shù) for ( int i = 0; i sz; i+ ) for ( int j = 0; j sz; j+ )

34、 if（i = j）Edgeij = 0; else Edgeij = MaxDist; CurrentEdges = 0;Data StructureSoftware College Northeastern University44template DistType Graph :GetWeight( int v1, int v2 ) /給出以頂點(diǎn)給出以頂點(diǎn) v1 和和 v2 為兩端點(diǎn)的邊上的權(quán)值為兩端點(diǎn)的邊上的權(quán)值if ( v1 != -1 & v2 != -1 ) return Edgev1v2; else return 0; Data StructureSoftware Co

35、llege Northeastern University45template int Graph:GetFirstNeighbor ( const int v ) /給出頂點(diǎn)位置為 v 的第一個(gè)鄰接頂點(diǎn)的位置 if ( v != -1 ) for ( int col = 0; col 0 & Edgevcol max ) return col; return -1; Data StructureSoftware College Northeastern University46template int Graph :GetNextNeighbor ( int v1, int v2 )

36、 /給出頂點(diǎn)給出頂點(diǎn)v1的某鄰接頂點(diǎn)的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) int col; if ( v1 != -1 & v2 != -1 ) for ( col = v2+1; col 0 & Edgev1col max ) return col; return -1;Data StructureSoftware College Northeastern University47Storing the adjacency matrix as an ordinary array is generally very wasteful.yThe size of the

37、 array will always be N2, where N is the number of vertices.yThe maximum number of edges possible is N2, and this only occurs in a loop digraph where every vertex is adjacent to itself and every other vertex. This is usually a very uninteresting graph.Representation of the Adjacency MatrixData Struc

38、tureSoftware College Northeastern University48z For each vertex, keep a list of all adjacent vertices.z For sparse graphs only.z Space requirement is (E+N), where E is the number of edges and N is the number of vertices.An Alternative Adjacency ListData StructureSoftware College Northeastern Univers

39、ity49represent G by an array HEAD, where HEADi is a pointer to the adjacency list for vertex i.Adjacency List of Directed GraphData StructureSoftware College Northeastern University50 zthe adjacency matrix for a graph is symmetric. In the adjacency list representation if (i, j) is an edge, then vert

40、ex j is on the list for vertex i and vertex i is on the list for vertex j.Adjacency List of Undirected GraphData StructureSoftware College Northeastern University51example V0 V4 V3 V1 V22 0 1 2 3 4m-1V0V1V2V3V413422110034Adjacency List of Undirected GraphData StructureSoftware College Northeastern U

41、niversity52 V0 V7 V6 V5 V4 V3 V2 V1 0 1 2 3 4 5 6 7V0V1V2V3V4V5V6V7121717056304265243例例Data StructureSoftware College Northeastern University53z The adjacency list for a vertex i is a list, in some order, of all vertices adjacent to i.z The adjacency list representation of a digraph requires storage

42、 proportional to sum of the number of vertices plus the number of arcsAdjacency List of Directed GraphData StructureSoftware College Northeastern University54Inverse Adjacency List of Directed GraphData StructureSoftware College Northeastern University55 Adjacency ListThe arcs start from the same ve

43、rtex stored in the sequential listV0V1V2V31230 0 1 2 3m-1example V0 V1 V2 V3Data StructureSoftware College Northeastern University56Inverse Adjacency ListV0V1V2V3 0 1 2 3m-10023example V0 V1 V2 V3Data StructureSoftware College Northeastern University57Adjacency Lists vs. Adjacency MatrixzSpace requi

44、rements have been discussed in previous notes.yAdjacency matrix O(N2)yAdjacency list O(E + N)yIf the graph is sparse, and there are not many edges, then adjacency lists will probably be more space efficient than adjacency matrices. yIf the graph is dense, and the number of edges is O(N2), then the a

45、djacency matrix will probably be more space efficient. Data StructureSoftware College Northeastern University58Adjacency Lists vs. Adjacency Matrix (cont)zTime requirementsData StructureSoftware College Northeastern University59const int DefaultSize = 10;template class Graph;template struct Edge fri

46、end class Graph; int dest; DistType cost; Edge *link; Edge ( ) Edge ( int D, DistType C ) : dest (D), cost (C), link (NULL) int operator != ( Edge& E ) const return dest != E.dest; Data StructureSoftware College Northeastern University60template struct Vertex friend class Graph; NameType data; E

47、dge *adj;template class Graph private: Vertex *NodeTable; int NumVertices; int MaxNumVertices;Data StructureSoftware College Northeastern University61 int NumEdges; int GetVertexPos ( NameType & vertex );public: Graph ( int sz ); Graph ( ); int GraphEmpty ( ) const return NumVertices = 0; int Gr

48、aphFull ( ) const return NumVertices = MaxNumVertices; NameType GetValue ( int i ) return i = 0 & i NumVertices ? NodeTablei.data : NULL; int NumberOfVertices ( ) return NumVertices; Data StructureSoftware College Northeastern University62 int NumberOfEdges ( ) return NumEdges; void InsertVertex

49、 ( NameType & vertex ); void RemoveVertex ( int v ); void InsertEdge ( int v1, int v2, DistType weight ); void RemoveEdge ( int v1, int v2 ); DistType GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 );Data StructureSoftware College Northeastern

50、University63Adjacency List of NetWorkConstructor and Deconstructortemplate Graph :Graph ( int sz = DefaultSize ) : NumVertices (0), MaxNumVertices (sz), NumEdges (0)Data StructureSoftware College Northeastern University64 int n, e, k, j; NameType name, tail, head; DistType weight; NodeTable = /創(chuàng)建頂點(diǎn)表

51、創(chuàng)建頂點(diǎn)表 new VertexMaxNumVertices; cin n; /輸入頂點(diǎn)個(gè)數(shù)輸入頂點(diǎn)個(gè)數(shù) for ( int i = 0; i name; InsertVertex ( name ); cin e; /輸入邊條數(shù)輸入邊條數(shù) for ( i = 0; i tail head weight; k = GetVertexPos ( tail ); j = GetVertexPos ( head ); InsertEdge ( k, j, weight ); Data StructureSoftware College Northeastern University65template

52、 Graph : Graph ( ) for ( int i = 0; i NumVertices; i+ ) Edge *p = NodeTablei.adj; while ( p != NULL ) /逐條邊釋放逐條邊釋放 NodeTablei.adj = plink; delete p; p = NodeTablei.adj; delete NodeTable; /釋放頂點(diǎn)表釋放頂點(diǎn)表V0V1V2V31230 0 1 2 3m-1Data StructureSoftware College Northeastern University66template int Graph :GetV

53、ertexPos ( const NameType & vertex ) / for ( int i =0; i NumVertices; i+ ) if ( NodeTablei.data = vertex ) return i; return -1;Data StructureSoftware College Northeastern University67template int Graph :GetFirstNeighbor ( int v ) /查找頂點(diǎn)查找頂點(diǎn) v 第一個(gè)鄰接頂點(diǎn)在鄰接表中的位置第一個(gè)鄰接頂點(diǎn)在鄰接表中的位置 if ( v != -1 ) /若頂點(diǎn)存在若頂

54、點(diǎn)存在 Edge *p = NodeTablev.adj; if ( p != NULL ) return pdest; return -1; /若頂點(diǎn)不存在若頂點(diǎn)不存在Data StructureSoftware College Northeastern University68template int Graph : GetNextNeighbor ( int v1, int v2 ) / if ( v1 != -1 ) Edge *p = NodeTablev1.adj; while ( p != NULL ) if ( pdest = v2 & plink != NULL )

55、return plinkdest; else p = plink; return -1; if ( pdest = v2) if (plink != NULL ) return plinkdest; else return -1;else else p = plink;Data StructureSoftware College Northeastern University69template DistType Graph :GetWeight ( int v1, int v2) / if ( v1 != -1 & v2 != -1 ) Edge *p = NodeTablev1.a

56、dj; while ( p != NULL ) if ( pdest = v2 ) return pcost; else p = plink; return MaxCost;Data StructureSoftware College Northeastern University70 mark vertex1 vertex2 path1 path2Adjacency MultiList of Undirected GraphData StructureSoftware College Northeastern University71yVertex node vertices list is

57、 sequential list. Every node has two members. data store the information about vertex and Firstout point to the first edge come from this vertex. data FirstoutData StructureSoftware College Northeastern University72example V1 V5 V4 V2 V3 0 1 2 3 4m-1V1V2V3V4V5103012321442Data StructureSoftware Colle

58、ge Northeastern University73zAbout directed graphyArc nodepath1 point to the next vertex which has the same source with this vertex.Path2 point to the next vertex which has the same target with this vertex. mark vertex1 vertex2 path1 path2Data StructureSoftware College Northeastern University74yVert

59、ex node Every vertex represented by a node. It is the head of in-edge list and out-edge listMember data store information about this vertex.Firstin point to the first edge start from this vertexFirstout point to the first edge end with this vertex。 data Firstin FirstoutData StructureSoftware College

60、 Northeastern University75Data StructureSoftware College Northeastern University76Two traversal method of binary treeGraph TraversalData StructureSoftware College Northeastern University77Suppose we have an undirected graph G in which all vertices are initially marked unvisited. Depth-first search works by selecting one vertex v of G as a start vertex; v is ma