數(shù)據(jù)結(jié)構(gòu)r8.ppt

1、Data Structure,Software College Northeastern University,1,Chapter 8,Graph,Data Structure,Software College Northeastern University,2,D,C,B,C,d,a,b,e,g,f,Pregal River,柯尼斯堡7橋問題,Kneiphof島 A,Data Structure,Software College Northeastern University,3,A,B,C,D,d,c,a,b,e,g,f,Data Structure,Software College No

2、rtheastern University,4,8.1 Graph Terminology 8.2 Representation of Graphs 8.2 Graph Traversal 8.3 Minimum Spanning Tree 8.4 Shortest-Path Algorithms 8.5 Network Flow Problems,Data Structure,Software College Northeastern University,5,Graph Terminology,A graph G( V, E ) consists of a set V of vertice

3、s, V, and a set E of edges, E. Each edge is a pair( v, w),where v, w V .If the pair is ordered, then the graph is directed(有向圖). Else the graph is undirected（無向圖）. G( V, E ) V is the set of vertices E = (x, y) | x, y V Or E = | x, y V void InsertVertex ( Type ,Representing Graphs,Data Structure,Soft

4、ware College Northeastern University,35,It should store 1) vertices 2) edges,Graph G=, V=v0,v1,v2, vn-1 the label of a vertex is its index,vertices label,Representing Graphs,Data Structure,Software College Northeastern University,36,The adjacency matrix( a matrix of what is adjacent to what) Vertice

5、s are mapped to integers 0N-1 An N-by-N matrix A is defined such that,Adjacency Matrix,Data Structure,Software College Northeastern University,37,Data Structure,Software College Northeastern University,38,0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0,0 1 1 0 0 0 0 0 0 0 0 1 0 0 0,Undirected graph ha

6、s symmetrical adjacency matrix. Degree of node i Aij(j=0n-1) Aji(j=0n-1),Out-degree Aij(j=0n-1) in-degree Aji(j=0n-1),Data Structure,Software College Northeastern University,39,Adjacency Matrix of network,Data Structure,Software College Northeastern University,40,Graph ADT with Adjacency Matrix cons

7、t int MaxNumEdges = 50; const int MaxNumVertices = 10; template class Graph private: SeqList VerticesList (MaxNumVertices); DistType EdgeMaxNumVerticesMaxNumVertices; int CurrentEdges; int FindVertex ( SeqList ,Data Structure,Software College Northeastern University,41,int GetVertexPos ( Const NameT

8、ype ,Data Structure,Software College Northeastern University,42,NameType GetValue ( int i ) return i = 0 ,Data Structure,Software College Northeastern University,43,Some Graph Operation const int MaxDist = 0 xFFFF； template Graph : Graph( int sz) /構(gòu)造函數(shù) for ( int i = 0; i sz; i+ ) for ( int j = 0; j

9、sz; j+ ) if（i = j）Edgeij = 0; else Edgeij = MaxDist; CurrentEdges = 0; ,Data Structure,Software College Northeastern University,44,template DistType Graph : GetWeight( int v1, int v2 ) /給出以頂點(diǎn) v1 和 v2 為兩端點(diǎn)的邊上的權(quán)值 if ( v1 != -1 ,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0,Data Structure,Software

10、College Northeastern University,45,template int Graph: GetFirstNeighbor ( const int v ) /給出頂點(diǎn)位置為 v 的第一個(gè)鄰接頂點(diǎn)的位置 if ( v != -1 ) for ( int col = 0; col 0 ,0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0,Data Structure,Software College Northeastern University,46,template int Graph : GetNextNeighbor ( int

11、v1, int v2 ) /給出頂點(diǎn)v1的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn) int col; if ( v1 != -1 ,0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0,Data Structure,Software College Northeastern University,47,Storing the adjacency matrix as an ordinary array is generally very wasteful. The size of the array will always be N2, where N is the

12、number of vertices. The 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 Matrix,Data Structure,Software College Northeastern Univ

13、ersity,48,For each vertex, keep a list of all adjacent vertices. For sparse graphs only. Space requirement is (E+N), where E is the number of edges and N is the number of vertices.,An Alternative Adjacency List,Data Structure,Software College Northeastern University,49,represent G by an array HEAD,

14、where HEADi is a pointer to the adjacency list for vertex i. Head ： edge：,Adjacency List of Directed Graph,Data Structure,Software College Northeastern University,50,the adjacency matrix for a graph is symmetric. In the adjacency list representation if (i, j) is an edge, then vertex j is on the list

15、 for vertex i and vertex i is on the list for vertex j.,Adjacency List of Undirected Graph,Data Structure,Software College Northeastern University,51,If E then E,example,1,0,下標(biāo) data adj,Adjacency List of Undirected Graph,Data Structure,Software College Northeastern University,52,0 1 2 3 4 5 6 7,V0 V

16、1 V2 V3 V4 V5 V6 V7,例,Data Structure,Software College Northeastern University,53,The adjacency list for a vertex i is a list, in some order, of all vertices adjacent to i. The adjacency list representation of a digraph requires storage proportional to sum of the number of vertices plus the number of

17、 arcs,Adjacency List of Directed Graph,Data Structure,Software College Northeastern University,54,Inverse Adjacency List of Directed Graph In the adjacency list, the ith edge list represent all the edges start from vertex i. it is out-edges list(出邊表) In the inverse adjacency list, all the edges in t

18、he ith list is end with vertex i. it is in-edges list(入邊表)。,Data Structure,Software College Northeastern University,55,Adjacency List The arcs start from the same vertex stored in the sequential list,下標(biāo) data adj,0 1 2 3 m-1,example,Data Structure,Software College Northeastern University,56,Inverse A

19、djacency List all the arcs with the same tail will be stored in a list,example,Data Structure,Software College Northeastern University,57,Adjacency Lists vs. Adjacency Matrix,Space requirements have been discussed in previous notes. Adjacency matrix O(N2) Adjacency list O(E + N) If the graph is spar

20、se, and there are not many edges, then adjacency lists will probably be more space efficient than adjacency matrices. If the graph is dense, and the number of edges is O(N2), then the adjacency matrix will probably be more space efficient.,Data Structure,Software College Northeastern University,58,A

21、djacency Lists vs. Adjacency Matrix (cont),Time requirements,Data Structure,Software College Northeastern University,59,Graph ADT with Adjacency List const int DefaultSize = 10; template class Graph; template struct Edge friend class Graph; int dest; DistType cost; Edge *link; Edge ( ) Edge ( int D,

22、 DistType C ) : dest (D), cost (C), link (NULL) int operator != ( Edge ,Data Structure,Software College Northeastern University,60,template struct Vertex friend class Graph; NameType data; Edge *adj; template class Graph private: Vertex *NodeTable; int NumVertices; int MaxNumVertices;,Data Structure

23、,Software College Northeastern University,61,int NumEdges; int GetVertexPos ( NameType ,Data Structure,Software College Northeastern University,62,int NumberOfEdges ( ) return NumEdges; void InsertVertex ( NameType ,Data Structure,Software College Northeastern University,63,Adjacency List of NetWork

24、,Constructor and Deconstructor template Graph : Graph ( int sz = DefaultSize ) : NumVertices (0), MaxNumVertices (sz), NumEdges (0),Data Structure,Software College Northeastern University,64,int n, e, k, j; NameType name, tail, head; DistType weight; NodeTable = /創(chuàng)建頂點(diǎn)表 new VertexMaxNumVertices; cin

25、n; /輸入頂點(diǎn)個(gè)數(shù) for ( int i = 0; i name; InsertVertex ( name ); cin e; /輸入邊條數(shù) for ( i = 0; i tail head weight; k = GetVertexPos ( tail ); j = GetVertexPos ( head ); InsertEdge ( k, j, weight ); ,Data Structure,Software College Northeastern University,65, template Graph : Graph ( ) for ( int i = 0; i *p =

26、 NodeTablei.adj; while ( p != NULL ) /逐條邊釋放 NodeTablei.adj = plink; delete p; p = NodeTablei.adj; delete NodeTable; /釋放頂點(diǎn)表 ,Data Structure,Software College Northeastern University,66,template int Graph : GetVertexPos ( const NameType ,Data Structure,Software College Northeastern University,67,templa

27、te int Graph : GetFirstNeighbor ( int v ) /查找頂點(diǎn) v 第一個(gè)鄰接頂點(diǎn)在鄰接表中的位置 if ( v != -1 ) /若頂點(diǎn)存在 Edge *p = NodeTablev.adj; if ( p != NULL ) return pdest; return -1; /若頂點(diǎn)不存在 ,Data Structure,Software College Northeastern University,68,template int Graph : GetNextNeighbor ( int v1, int v2 ) /查找頂點(diǎn) v1 在鄰接頂點(diǎn) v2 后下

28、一個(gè)鄰接頂點(diǎn) if ( v1 != -1 ) Edge *p = NodeTablev1.adj;,while ( p != NULL ) if ( pdest = v2 /沒有查到下一個(gè)鄰接頂點(diǎn)返回-1 ,if ( pdest = v2) if (plink != NULL ) return plinkdest; else return -1; else else p = plink;,Data Structure,Software College Northeastern University,69,template DistType Graph : GetWeight ( int v1,

29、 int v2) /取兩端點(diǎn)為 v1 和 v2 的邊上的權(quán)值 if ( v1 != -1 ,Data Structure,Software College Northeastern University,70,In adjacency multilist of undirected graph, every edge represented by a edge node. It is convenient to traverse all the edges. About undirected graph Edge node,mark vertex1 vertex2 path1 path2,ma

30、rk 是記錄是否處理過的標(biāo)記 vertex1和vertex2是依附于該邊的兩頂點(diǎn)位置 path1域是鏈接指針，指向下一條依附于頂點(diǎn)vertex1的邊 path2也是鏈接指針，指向下一條依附于頂點(diǎn)vertex2的邊 需要時(shí)還可設(shè)置一個(gè)存放與該邊相關(guān)的權(quán)值的域 cost,Adjacency MultiList of Undirected Graph,Data Structure,Software College Northeastern University,71,Vertex node vertices list is sequential list. Every node has two me

31、mbers. data store the information about vertex and Firstout point to the first edge come from this vertex.,data Firstout,Data Structure,Software College Northeastern University,72,example,Data Structure,Software College Northeastern University,73,About directed graph Arc node path1 point to the next

32、 vertex which has the same source with this vertex. Path2 point to the next vertex which has the same target with this vertex.,Data Structure,Software College Northeastern University,74,Vertex node Every vertex represented by a node. It is the head of in-edge list and out-edge list Member data store

33、 information about this vertex. Firstin point to the first edge start from this vertex Firstout point to the first edge end with this vertex 。,data Firstin Firstout,Data Structure,Software College Northeastern University,75,Adjacency multilist,Data Structure,Software College Northeastern University,

34、76,Visit all the vertices only one time,Two traversal method of binary tree depth first Traversal breath first Traversal,Graph Traversal,Data Structure,Software College Northeastern University,77,Suppose we have an undirected graph G in which all vertices are initially marked unvisited. Depth-first

35、search works by selecting one vertex v of G as a start vertex; v is marked visited. Then each unvisited vertex adjacent to v is searched in turn, using depth-first search recursively.,The second,First adjacent vertex,Recursion,Depth-First Traversal,Data Structure,Software College Northeastern Univer

36、sity,78,V0,V1,V3,V7,V4,V2,V5,V6,The depth sequence is not unique,example,Depth traversal start at v0,V0,V1,V4,V7,V3,V2,V5,V6,Data Structure,Software College Northeastern University,79,V6,If the storage structure is determined, the sequence is unique,Depth first : V0,V1,V3,V7,V4,V2,V5,V6,Data Structu

37、re,Software College Northeastern University,80,To avoid visit a vertex repeatedly, set an array visited to remember whether the vertex was visited or not. when the vertex i was visited, then change visited i from 0 to 1.,Depth-First Traversal,Data Structure,Software College Northeastern University,8

38、1,example,Depth-First Traversal,Data Structure,Software College Northeastern University,82,template void Graph : DFS ( ) int * visited = new int NumVertices; for ( int i = 0; i NumVertices; i+ ) visited i = 0; /訪問標(biāo)記數(shù)組 visited 初始化 DFS (0, visited ); delete visited; /釋放 visited ,Depth-First Traversal,

39、Data Structure,Software College Northeastern University,83,template void Graph : DFS ( const int v, int visited ) ,cout GetValue (v) ; /訪問頂點(diǎn) v visitedv = 1; /頂點(diǎn) v 作訪問標(biāo)記 int w = GetFirstNeighbor (v); /取 v 的第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) DFS ( w, visited ); /若頂點(diǎn) w 未訪問過, 遞歸訪問頂

40、點(diǎn) w w = GetNextNeighbor ( v, w ); /取頂點(diǎn) v 的排在 w 后面的下一個(gè)鄰接頂點(diǎn) ,Data Structure,Software College Northeastern University,84,Algorithm analysis,Assume there are n vertices and e edges If represent the graph by adjacency list. There are 2e edge nodes. So time for scanning all the edges is O(e). Visit the ve

41、rtices one by one, so total time for traversal is O(n+e). Change to adjacency matrix, the time to search all the edges adhere to a vertex is O(n). Then traverse all the vertices need O(n2).,Data Structure,Software College Northeastern University,85,Start from vertex vi. it is unvisited. 1）visit vi 2

42、）visit all the neighbors of vi :w1 ,w2 , wk 3）start from these vertices in turn until all the vertices were visited,The second neighbor,The first neighbor,Breadth-First Traversal,Data Structure,Software College Northeastern University,86,The path of the first sequence,example,Start from V0,V0,V1,V2,

43、V3,V4,V5,V6,V7 V0,V2 ,V1,V5,V6,V3,V4,V7,Data Structure,Software College Northeastern University,87,breadth-first traversal breadth-first spanning tree,Breadth-First Traversal,Data Structure,Software College Northeastern University,88,Breadth-first search will visit a number of vertices in each step.

44、 It has no backtrack. So breadth-first search isnt a recursive procedure. To avoid visit a vertex repeatedly, an array visited is used to mark the vertex visited.,Data Structure,Software College Northeastern University,89,template void Graph : BFS ( int v ) int * visited = new intNumVertices; for (

45、int i = 0; i q; q.EnQueue (v); /訪問 v, 進(jìn)隊(duì)列,Breadth-First Traversal,Data Structure,Software College Northeastern University,90,while ( !q.IsEmpty ( ) ) /隊(duì)空搜索結(jié)束 v = q.DeQueue ( ); /不空, 出隊(duì)列 int w = GetFirstNeighbor (v); /取頂點(diǎn) v 的第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) /若該鄰接頂點(diǎn)未訪問過 cout Ge

46、tValue (w) ; /訪問 visitedw = 1; q.EnQueue (w); /進(jìn)隊(duì) w = GetNextNeighbor (v, w); /取頂點(diǎn) v 的排在 w 后面的下一鄰接頂點(diǎn) /重復(fù)檢測(cè) v 的所有鄰接頂點(diǎn) /外層循環(huán)，判隊(duì)列空否 delete visited; ,Data Structure,Software College Northeastern University,91,Analysis,If the graph represented by adjacent list, total time is d0 + d1 + + dn-1 = O(e) di is

47、 the degree of vertex i If by adjacent matrix, we need check n elements for any visited vertex. Then total time is O(n2)。,Data Structure,Software College Northeastern University,92,In a non-connected undirected graph, start from a vertex in it only can visit the vertices in the same connected compon

48、ent( maximal connected subgraph) Search all the connected component Search every vertex in the graph. If the vertex has been visited, it must be in a connected component. Else start from this vertex to traverse the graph, well get another connected component,Connected component,Data Structure,Softwa

49、re College Northeastern University,93,In a non-connected undirected graph, the spanning trees of all the connected components form the spanning forest.,Data Structure,Software College Northeastern University,94,Connected components template void Graph : Components ( ) int *visited = new intNumVertic

50、es; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited 初始化 for ( i = 0; i NumVertices; i+ ) if ( !visitedi ) /檢測(cè)所有頂點(diǎn)是否訪問過 DFS ( i, visited ); /從未訪問的頂點(diǎn)出發(fā)訪問 OutputNewComponent ( ); /輸出一個(gè)連通分量 ,delete visited; /釋放visited ,Data Structure,Software College Northeastern University,95,Minimum Cost S

51、panning Tree(最小生成樹 ),When graph G is connected, a depth first or breadth first search starting at any vertex will visit all the vertices in G A spanning tree is any tree that consists solely of edges in G and that includes all the vertices In the minimum spanning tree n vertices and n-1 edges it is

52、acyclic It has the lowest total cost.,Data Structure,Software College Northeastern University,96,5,If we need to wire a house with a minimum of cable, how to solve it?.,3,6,5,2,1,6,5,4,6,example,solution a minimum spanning tree problem needs to be solved,How to form minimum spanning tree?,？,There ar

53、e two basic algorithms to solve this problem; both are greedy. Prims Algorithm and Kruskals Algorithm,Data Structure,Software College Northeastern University,97,貪婪技術(shù)(Greedy Technique),貪婪技術(shù)定義及其解題步驟 貪婪技術(shù)常見算法 Prim算法 Kruskal算法 Dijkstra算法 哈夫曼樹 背包問題 掌握貪婪技術(shù)的原理、效率分析方法,Data Structure,Software College Northea

54、stern University,98,找零錢問題(change-making problem),用當(dāng)?shù)孛骖~為d1d2dm的最少數(shù)量的硬幣找出金額為n的零錢。 如d1=25,d2=10,d3=5,d4=1，n=48 該問題的一個(gè)解是： 1個(gè)25，2個(gè)10，3個(gè)1，且該解是最優(yōu)的。 這種方法稱為貪婪法，建議通過一系列步驟來構(gòu)造問題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問題的完全解。 必須滿足：可行、局部最優(yōu)、不可取消 貪心方法是作出在當(dāng)前看來最好的選擇，即所作的選擇只是局部最優(yōu)選擇。 希望從局部的最優(yōu)選擇得到整體最優(yōu)解。,Data Structure,Software College

55、 Northeastern University,99,貪婪算法原理,在傳統(tǒng)貪婪算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都做出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。做出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。 貪心思想的本質(zhì)是每次都形成局部最優(yōu)解，就是每次都處理出一個(gè)最好的方案。即，貪婪法建議通過一系列步驟來構(gòu)造問題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問題的完全解為止。,Data Structure,Software College Northeastern University,100,貪婪算法原理,這個(gè)技術(shù)的核心是，所做的每一步選擇都必須滿足：

56、可行的：即它必須滿足問題的約束。 局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇。 不可取消：即選擇一旦做出，在算法的后面步驟中就無法改變了。,Data Structure,Software College Northeastern University,101,Kruskals Algorithm,Suppose a connected graph G=(V, E) Build a minmum cost spanning tree T by adding edges to T one at a time. Select the edges for inclusion in T in

57、nondecreasing order of the cost. An edge is added to T if it does not form a cycle Since G is connected and has n0 vertices, exactly n-1 edges will be selected.,Data Structure,Software College Northeastern University,102,Sequence of edges added by Kruskals algorithm,Data Structure,Software College N

58、ortheastern University,103,Well use MinHeap(最小堆) DisjointSets(并查集),Possible representations of S1 S2,index parent,Set S1, S2 and S3,-1 4 -1 2 -1 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,Kruskals Algorithm,Data Structure,Software College Northeastern University,104,We also need to maintain a set of connected components C. The oper