数据结构与程序设计(王丽苹)31-graph.ppt
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/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(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 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 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,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 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 there 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 P572Adjacency 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,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 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 graphadjacency 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,数据结构与程序设计,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: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,数据结构与程序设计,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 Vertex*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 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 traversal 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 visited.,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/2023,数据结构与程序设计,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,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 Probing 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 neighbor,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 is 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,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 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,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 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,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,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 vertex 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,it 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,数据结构与程序设计,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: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 neighbor: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,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: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 implemented 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,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 queueVisited 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 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 Traversal(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 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 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 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,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 Vertices 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,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,
