数据结构与程序设计(王丽苹)31-graph.ppt

《数据结构与程序设计(王丽苹)31-graph.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计(王丽苹)31-graph.ppt（58页珍藏版）》请在三一办公上搜索。

1、9/11/2023,数据结构与程序设计,1,数据结构与程序设计(31)Chapter12 Graphs,王丽苹,9/11/2023,数据结构与程序设计,2,Graphs example:Northwest Airline Flight,ShenYang,Ji Nan,ShanHai,Bei Jing,WuHan,Xi an,Lan Zhou,Wu LU Mu Qi,9/11/2023,数据结构与程序设计,3,Graphs example:Computer Network Or Internet,ECNU,Regional Network,Intel,UNT,FuDan University,9

2、/11/2023,数据结构与程序设计,4,Application,Traveling SalemanFind the shortest path that connects all cities without a loop.,Start,9/11/2023,数据结构与程序设计,5,Concepts of Graphs,edges(weight),node or vertex,9/11/2023,数据结构与程序设计,6,Graph Definition,A graph G=(V,E)is composed of:V:set of vertices(nodes 节点)E:set of edges

3、(arcs 边)connecting the vertices in VAn edge e=(u,v)is a pair of verticesExample:,a,b,c,d,e,V=a,b,c,d,eE=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e),9/11/2023,数据结构与程序设计,7,Undirected vs.Directed Graph,Undirected Graph edge has no oriented,Directed Graph edge has oriented vertex,9/11/2023,数据结构与程序设计,8,The

4、 degree（度）of a vertex is the number of edges to that vertexFor directed graph,the in-degree(入度)of a vertex v is the number of edgesthat have v as the headthe out-degree(出度)of a vertex v is the number of edgesthat have v as the tailif di is the degree of a vertex i in a graph G with n vertices and e

5、edges,the number of edges is,Degree of a Vertex,Hint:Adjacent vertices are counted twice.,9/11/2023,数据结构与程序设计,9,Simple Path（简单路径）,A simple path is a path such that all vertices are distinct,except that the first and the last could be the same.ABCD is a simple path,B,C,D,A,path,9/11/2023,数据结构与程序设计,10

6、,Cycle（环）,A cycle is a path that starts and ends at the same point.For undirected graph,the edges are distinct.CBDC is a cycle,B,C,D,A,9/11/2023,数据结构与程序设计,11,Connected vs.Unconnected Graph：,Connected Graph连通图,Unconnected Graph非连通图,A graph is called connected if there is a path from any vertex to any

7、 other vertex.,9/11/2023,数据结构与程序设计,12,Weighted Graph（带权图）,Weighted graph:a graph with numbers assigned to its edgesWeight:cost,distance,travel time,hop,etc.,0,1,3,2,20,10,1,5,4,9/11/2023,数据结构与程序设计,13,strongly connected Vs.Weakly connected(强连通和弱连通),A directed graph is called strongly connected if the

8、re is a directed path from any vertex to any other vertex.If we suppress the direction of the edges and the resulting undirected graph is connected,we call the directed graph weakly connected.,9/11/2023,数据结构与程序设计,14,Representation Of Graph,Two representationsAdjacency Matrix/Table 12.2.1 P572Adjacen

9、cy List 12.2.2 P574,9/11/2023,数据结构与程序设计,15,Adjacency Matrix/Table,Assume N nodes in graphUse Matrix A0N-10N-1if vertex i and vertex j are adjacent in graph,Aij=1,otherwise Aij=0if vertex i has a loop,Aii=1if vertex i has no loop,Aii=0,9/11/2023,数据结构与程序设计,16,Implementation of Sets Declaration:(1)P573

10、,Digraph as a bit-string set:template struct Set bool is_elementmax_set;template class Digraph int count;/number of vertices,at most max size Set neighborsmax_size;,9/11/2023,数据结构与程序设计,17,Adjacency Matrix/Table Declaration(2)P574,Digraph as an adjacency table:template class Digraph int count;/number

11、 of vertices,at most max size bool adjacencymax_sizemax_size;,9/11/2023,数据结构与程序设计,18,Adjacency Matrix/Table Declaration(2),9/11/2023,数据结构与程序设计,19,Example of Adjacency Matrix/Table 邻接矩阵,0,1,3,2,So,Matrix A=,0 1 1 01 0 1 11 1 0 10 1 1 0,9/11/2023,数据结构与程序设计,20,Undirected vs.Directed,Undirected graphadj

12、acency matrix is symmetricAij=AjiDirected graphadjacency matrix may not be symmetricAijAji,9/11/2023,数据结构与程序设计,21,Directed Graph,0,1,3,2,So,Matrix A=,0 1 1 10 0 0 10 0 0 10 0 0 0,9/11/2023,数据结构与程序设计,22,Weighted Graph,0,1,3,2,20,10,1,5,4,So,Matrix A=,0 20 10 120 0 0 510 0 0 4 1 5 4 0,9/11/2023,数据结构与程

13、序设计,23,Adjacency List 邻接表,An array of listthe ith element of the array is a list of vertices that connect to vertex i,0,1,3,2,vertex 0 connect to vertex 1,2 and 3vertex 1 connects to 3vertex 2 connects to 3,9/11/2023,数据结构与程序设计,24,Weighted Graph,Weighted graph:extend each node with an addition field:

14、weight,0,1,3,2,20,10,1,5,4,0,1,2,3,1,10,2,20,3,1,0,10,3,4,0,20,3,5,0,1,1,4,2,5,9/11/2023,数据结构与程序设计,25,Adjacency List implementation,typedef int Vertex;template class Digraph int count;/number of vertices,at most max_sizeList neighborsmax_size;,9/11/2023,数据结构与程序设计,26,Adjacency List,9/11/2023,数据结构与程序设

15、计,27,Linked Implementation十字链表的实现,class Edge;/forward declarationclass Vertex Edge*first_edge;/start of the adjacency listVertex*next_vertex;/next vertex on the linked list;class Edge Vertex*end_point;/vertex to which the edge pointsEdge*next_edge;/next edge on the adjacency list;class Digraph Verte

16、x*first_vertex;/header for the list of vertices;P576 figure 12.5(a),9/11/2023,数据结构与程序设计,28,Adjacency List implementation,9/11/2023,数据结构与程序设计,29,Comparison Of Representations,9/11/2023,数据结构与程序设计,30,Graph Traversal Algorithms,Depth-first traversal of a graph is roughly analogous to preorder traversal

17、of an ordered tree.Suppose that the traversal has just visited a vertex v,and let w1;w2;:;wk be the vertices adjacent to v.Then we shall next visit w1 and keep w2;:;wk waiting.After visiting w1,we traverse all the vertices to which it is adjacent before returning to traverse w2;:;wk.Breadth-first tr

18、aversal of a graph is roughly analogous to level-by-level traversal of an ordered tree.If the traversal has just visited a vertex v,then it next visits all the vertices adjacent to v,putting the vertices adjacent to these in a waiting list to be traversed after all vertices adjacent to v have been v

19、isited.,9/11/2023,数据结构与程序设计,31,Graph Traversal Algorithms,9/11/2023,数据结构与程序设计,32,Graph Traversal p577 F12.6 Depth-First Algorithm,template void Digraph:depth_first(void(*visit)(Vertex,9/11/2023,数据结构与程序设计,33,Graph Traversal p577 F12.6 Depth-First Algorithm,template void Digraph:traverse(Vertex,9/11/2

20、023,数据结构与程序设计,34,Depth First Traversal,ExampleAs neighbor:B,C,EBs neighbor:A,C,FCs neighbor:A,B,DDs neighbor:E,C,FEs neighbor:A,DFs neighbor:B,Dstart from vertex A,A,B,C,E,F,D,9/11/2023,数据结构与程序设计,35,Depth First Traversal(Cont),Initial StateVisited Vertices Probing Vertices A Unvisited Vertices A,B,C

21、,D,E,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,A,stack,9/11/2023,数据结构与程序设计,36,Depth First Traversal(Cont),Peek a vertex from stack,it is A,mark it as visitedFind As first unvisited neighbor,push it into stackVisited Vertices A Pr

22、obing vertices A,B Unvisited Vertices B,C,D,E,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,B,A,stack,A,9/11/2023,数据结构与程序设计,37,Depth First Traversal(Cont),Peek a vertex from stack,it is B,mark it as visitedFind Bs first unvisited nei

23、ghbor,push it in stackVisited Vertices A,B Probing Vertices A,B,C Unvisited Vertices C,D,E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,C,B,A,stack,B,A,A,B,C,E,F,D,9/11/2023,数据结构与程序设计,38,Depth First Traversal(Cont),Peek a vertex from stack,it i

24、s C,mark it as visitedFind Cs first unvisited neighbor,push it in stackVisited Vertices A,B,C Probing Vertices A,B,C,D Unvisited Vertices D,E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,C,B,A,9/11/2023,数据结构与程序设计,39,De

25、pth First Traversal(Cont),Peek a vertex from stack,it is D,mark it as visitedFind Ds first unvisited neighbor,push it in stackVisited Vertices A,B,C,D Probing Vertices A,B,C,D,E Unvisited Vertices E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,

26、stack,A,B,C,E,F,D,D,C,B,E,A,D,C,B,A,9/11/2023,数据结构与程序设计,40,Depth First Traversal(Cont),Peek a vertex from stack,it is E,mark it as visitedFind Es first unvisited neighbor,no vertex found,Pop EVisited Vertices A,B,C,D,E Probing Vertices A,B,C,D Unvisited Vertices F,As neighbor:B C EBs neighbor:A C FC

27、s neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,D,C,B,E,A,9/11/2023,数据结构与程序设计,41,Depth First Traversal(Cont),Peek a vertex from stack,it is D,mark it as visitedFind Ds first unvisited neighbor,push it in stackVisited Vertices A,B,C,D,E Probing Vertices A,B,C

28、,D,FUnvisited Vertices F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,F,A,D,C,B,A,9/11/2023,数据结构与程序设计,42,Depth First Traversal(Cont),Peek a vertex from stack,it is F,mark it as visitedFind Fs first unvisited neighbor,no ve

29、rtex found,Pop FVisited Vertices A,B,C,D,E,F Probing Vertices A,B,C,DUnvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,D,C,B,F,A,9/11/2023,数据结构与程序设计,43,Depth First Traversal(Cont),Peek a vertex from stack,i

30、t is D,mark it as visitedFind Ds first unvisited neighbor,no vertex found,Pop DVisited Vertices A,B,C,D,E,F Probing Vertices A,B,C Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,C,B,A,D,C,B,A,9/11/2023,数据结构与程序设计

31、,44,Depth First Traversal(Cont),Peek a vertex from stack,it is C,mark it as visitedFind Cs first unvisited neighbor,no vertex found,Pop CVisited Vertices A,B,C,D,E,F Probing Vertices A,B Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor

32、:B D,stack,A,B,C,E,F,D,B,A,C,B,A,9/11/2023,数据结构与程序设计,45,Depth First Traversal(Cont),Peek a vertex from stack,it is B,mark it as visitedFind Bs first unvisited neighbor,no vertex found,Pop BVisited Vertices A,B,C,D,E,F Probing Vertices A Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbo

33、r:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,A,B,A,9/11/2023,数据结构与程序设计,46,Depth First Traversal(Cont),Peek a vertex from stack,it is A,mark it as visitedFind As first unvisited neighbor,no vertex found,Pop AVisited Vertices A,B,C,D,E,F Probing Vertices Unvisited Vertices,

34、As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,A,9/11/2023,数据结构与程序设计,47,Depth First Traversal(Cont),Now probing list is emptyEnd of Depth First TraversalVisited Vertices A,B,C,D,E,F Probing Vertices Unvisited Vertices,As neighbor:

35、B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,9/11/2023,数据结构与程序设计,48,Graph Traversal p577 F12.6Breadth-First Algorithm,template void Digraph:breadth_first(void(*visit)(Vertex,9/11/2023,数据结构与程序设计,49,Breadth First Traversal,Probing List is imp

36、lemented as queue(FIFO)ExampleAs neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B Dstart from vertex A,A,B,C,E,F,D,9/11/2023,数据结构与程序设计,50,Breadth First Traversal(Cont),Initial StateVisited Vertices Probing Vertices A Unvisited Vertices A,B,C,D,E,F,A,B,C,E

37、,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,A,queue,9/11/2023,数据结构与程序设计,51,Breadth First Traversal(Cont),Delete first vertex from queue,it is A,mark it as visitedFind As all unvisited neighbors,mark them as visited,put them into queueVisite

38、d Vertices AProbing Vertices B,C,E Unvisited Vertices D,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,A,queue,B,E,C,9/11/2023,数据结构与程序设计,52,Breadth First Traversal(Cont),Delete first vertex from queue,it is B,mark it as visitedFind Bs

39、 all unvisited neighbors,mark them as visited,put them into queueVisited Vertices A,B,Probing Vertices C,E,F Unvisited Vertices D,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,B,E,C,queue,C,F,E,9/11/2023,数据结构与程序设计,53,Breadth First Trav

40、ersal(Cont),Delete first vertex from queue,it is C,mark it as visitedFind Cs all unvisited neighbors,mark them as visited,put them into queueVisited Vertices A,B,C,Probing Vertices E,F,D Unvisited Vertices,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A

41、DFs neighbor:B D,C,F,E,queue,E,D,F,9/11/2023,数据结构与程序设计,54,Breadth First Traversal(Cont),Delete first vertex from queue,it is E,mark it as visitedFind Es all unvisited neighbors,no vertex foundVisited Vertices A,B,C,EProbing Vertices F,D Unvisited Vertices,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C

42、 FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,E,D,F,queue,F,D,9/11/2023,数据结构与程序设计,55,Breadth First Traversal(Cont),Delete first vertex from queue,it is F,mark it as visitedFind Fs all unvisited neighbors,no vertex foundVisited Vertices A,B,C,E,F Probing Vertices D Unvisited Vert

43、ices,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,F,D,queue,D,9/11/2023,数据结构与程序设计,56,Breadth First Traversal(Cont),Delete first vertex from queue,it is D,mark it as visitedFind Ds all unvisited neighbors,no vertex foundVisited Vertice

44、s A,B,C,E,F,D Probing Vertices Unvisited Vertices,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,D,queue,9/11/2023,数据结构与程序设计,57,Breadth First Traversal(Cont),Now the queue is emptyEnd of Breadth First TraversalVisited Vertices A,B,C,E,F

45、,D Probing Vertices Unvisited Vertices,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,queue,9/11/2023,数据结构与程序设计,58,Difference Between DFT&BFT,Depth First Traversal(DFT)order of visited:A,B,C,D,E,FBreadth First Traversal(BFT)order of visited:A,B,C,E,F,D,A,B,C,E,F,D,