7图(基础知识)-精品课件(PPT).ppt

第七章第七章图图 图的定义和术语图的定义和术语 图的存储结构图的存储结构 图的遍历图的遍历 图的连通性问题图的连通性问题 有向无环图及其应用有向无环图及其应用 最短路径最短路径(1)图: 是由一个顶点集 V和一个弧集(边集) R构成的数据结构。<v,w> 表示从 v 到 w 的一条弧,并称 v 为弧尾, w 为弧头。(v,w )表示一条边。§ § 图的定义和术语图的定义和术语图的相关术语: A B E C D (2)有向图: “弧”是有方向的,由顶点集和弧集构成是有向图。例如: 图G 1顶点集: {A,B,C,D,E} 弧集: {< A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> } B C A D F E (3)无向图:由顶点集和边集构成的图为无向图。例如:图G 2顶点集: {A, B, C, D, E, F} 边集: {( A,B ), ( A,E ),( B,E ), ( C,D ), ( D,F ),( B,F ), ( C,F )} 假设图中有 n个顶点,则: (4)完全图:含有 n(n-1)/2 条边的无向图。(5)有向完全图:含有 n(n-1) 条弧的有向图。(6)若边或弧的个数 e< nlogn ,则称作稀疏图,否则称作稠密图。 15 9721 11 2 (7)有向网:带权的有向图。(8)无向网:带权的无向图。 3AB EC F AEF B (9)子图:设图 G=(V,{VR}) 和 G?=(V ?,{VR ?}),且V ?? V, VR ?? VR , 则称 G?为 G 的子图。 AB EC F BC 无向图来说: 假若顶点 v 和顶点 w 之间存在一条边,则称顶点v和w互为邻接点,边(v,w )和顶点 v 和w 相关联。例如: TD(B) = 3 TD(A) = 2 A CDF E B ?顶点的度: 和顶点 v 关联的边的数目, 记为 TD(v) 。?顶点的出度: 以顶点 v为弧尾的弧的数目。 ABECF 有向图来说, ?顶点的入度: 以顶点 v为弧头的弧的数目。?顶点的度( TD )=出度( OD )+入度( ID )例如: ID(B) = 2 OD(B) = 1 TD(B) = 3 设图 G=(V,{VR}) 中的一个顶点序列(u=v i,0,v i,1, …, v i,m =w) ,其中(v i,j-1 ,v i,j)? VR, 1 ≤j≤ m, 则称从顶点 u 到顶点 w 之间存在一条路径。路径上边的数目称作路径长度。如:长度为 3的路径{A,B,C,F} 简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同的路径。 ABECF