《【精品数据结构】Graphs.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】Graphs.ppt（31页珍藏版）》请在三一文库上搜索。
1、Chapter 12,Graphs,Main topics,Definition of graphs and some terminology Three common graph representations Some algorithms,12.1 Definition and terminologies,Definition of graphs: Graph=(V, E) V: nonempty finite vertice set E: edge set Undirected praph: If the tuple denoting an edge is unordered, the
2、n (v1,v2) and (v2,v1) are the same edge.,12.1 Definition and terminologies,Directed graph: If the tuple denoting an edge is ordered, then (v1,v2) and (v2,v1) are different edges.,12.1 Definition and terminologies,Example:,V1,V2,V(G2)=V1,V2,V3 E(G2)=,V3,12.1 Definition and terminologies,We will not d
3、iscuss graphs of the following types,12.1 Definition and terminologies,2.Complete graph In an undirected graph with n nodes, the number of edges =n*(n-1)/2. If “=“ is satisfied, then it is called a complete undirect graph.,12.1 Definition and terminologies,In a directed graph with n nodes, the numbe
4、r of edges =n*(n-1). If “=“ is satisfied, then it is called a complete directed graph.,12.1 Definition and terminologies,3.degree di of vertex i, TD(v): is the number of edges incident on vertex i. In a directed graph : in-degree of vertex i is the number of edges incident to i, ID(v). out-degree of
5、 vertex i is the number of edges from the i, OD(v).,12.1 Definition and terminologies,TD(v)=ID(v)+OD(v) Generally,if there are n vertices and e edges in a graph, then e=(TD(vi)/2,v1,v2,v3,ID(v2)=1 OD(v2)=2,TD(v2)=3,i=1,n,12.1 Definition and terminologies,4. Subgraph Graph G=(V,E),G=(V,E), if VV, EE,
6、 and the vertices incident on the edges in E are in V, then G is the subgraph of G. For example:,1,3,4,2,1,1,3,3,1,4,12.1 Definition and terminologies,Another example:,V1,12.1 Definition and terminologies,5.path. A sequence of vertices P=i1,i2,ik is an i1 to ik path in the graph of digraph G=(V,E) i
7、ff the edge(ij,ij+1)is in E for every j, 1=jk. 6. Simple path and cycle A Simple path is a path in which all vertices except possibly the first and last , are different. A cycle is a simple path with the same start and end vertex.,12.1 Definition and terminologies,An example of a cycle,12.1 Definiti
8、on and terminologies,7.Connected graph false otherwise,12.2 ADT Graph and Digraph,Edges():return the number of edges in the graph Vertices():return the number of vertices in the graph Add(i,j): add the edge(i,j) to the graph Delete(i,j):delete the edge (i,j) Degree(i): return the degree of vertex i
9、InDegree(i): synonym for degree OutDegree(i): synonym for degree ,12.2 ADT Graph and Digraph,ADT 12.2 AbstractDataType Digraph instances a set V of vertices and a set E of edges operations Create(n): create a directed graph with n vertices and no edges Exist(i,j): return true if edge(i,j)exists; fal
10、se otherwise,12.2 ADT Graph and Digraph,Edges():return the number of edges in the graph Vertices():return the number of vertices in the graph Add(i,j): add the edge(i,j) to the graph Delete(i,j):delete the edge (i,j) InDegree(i): return the in-degree of vertex i OutDegree(i): return the out-degree o
11、f vertex i ,12.3 Representation of graphs and digraphs,1.Adjacency Matrix G=(V,E), V=V1,V2,Vn then the adjacency matrix of graph G: A(i,j)=,12.3 Representation of graphs and digraphs,For example: graph,V1,V2,V3,V4,1)Adjacency matrix of graph is a symmetric matrix 2) A(i,j)= A(j,i)=di (degree of vert
12、ex I),n,J=1,n,i=1,12.3 Representation of graphs and digraphs,Digraph,V1,V2,V5,V4,V3,1) A(i,j)= diout A(j,i)=diin,j=1,n,n,j=1,12.3 Representation of graphs and digraphs,Representation of networks, replace 1 with weights, others with ,W(i,j) If i!=j and ,E or(i,j)E otherwise,A(i,j)=,12.3 Representatio
13、n of graphs and digraphs,For example:,3,4,1,2,8,6,2,3,1,4,9,5,A(i,j)=, 1 4 9 2 3 5 8 6 ,12.3 Representation of graphs and digraphs,2. Linked-adjacency Lists reduce the storage requirement if the number of edges in the graph is small.,V1,V3,V2,V4,12.3 Representation of graphs and digraphs,Digraph:,V1,V2,V3,11,3,4,6,2,2 6,3 3 0,2 2 0,1 4 0,1 11,1 2 3,h,