资源描述：
《数据结构课件CD 第07章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章 图数据结构主讲教师：周时阳本章主要介绍串，它属于线性结构，是数据元素的内部结构确定为符号的特殊线性表。讨论串的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。重点研究串的概念、基本运算、顺序结构和链式存储结构及其主要运算的实现算法及其效率分析。内容摘要2重点讲解7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径小结37.1.1图的逻辑结构定义及术语图(Graph)是由V和E两个有限的集
2、合构成，记为：G=(V,E)。其中，V称为顶点集，E称为边集。7.1图的定义和基本术语数据元素数据元素集合D关系集合R边(Edge)：顶点的关系偶对。无向边(Edge)：关系偶对是无序的边。记为：(i,j)。有向边(Arc)：关系偶对是有序的边，也称为弧。记为：。ijij4无向图(UndirectedGraph)：无向边集的图。有向图(DirectedGraph)：有向边集的图。G1=(V,E)，其中，V={1、2、3、4、5}E={(1,2)、(1,3)、(2,3)、(3,4)、(3,5
3、)、(4,5)}12345G1:G2=(V,E)，其中，V={1、2、3、4}E={<1,3>、<2,1>、<2,4>、<3,2>、<4,1>、<4,3>}1245G2:5顶点的度(Degree)：与顶点U关联的边数，记为D(U)。对于有向图，以顶点U为始点的弧数称为顶点的出度，记为OD(U)；以顶点U为终点的弧数称为顶点的入度，记为ID(U)；顶点U的度为其出度和入度之和，即D(U)=OD(U)+ID(U)。12345G1:1245G2:对于图G1，D(1)=2，D(3)=4，D(2)=2，…对于
4、图G2，D(1)=OD(1)+ID(1)=1+2=3，…6无向完全图：具有n个顶点且有n(n-1)/2条边的无向图。有向完全图：具有n个顶点且有n(n-1)个弧的有向图。子图(Subgraph)：假设G＝(V,E)和G′＝(V′,E′),如果V′⊆V且E′⊆E，则称G′是G的子图。12345G1:12345G2:12345G3:1234G4:G2、G3和G4是G1的子图。G1、G3和G4是G2的子图。G3不是G4的子图。G4不是G3的子图。7路径(Path)：如果图G中两个顶点V和V′之间存在由边或
5、弧组成的通路，即对无向图存在(V,V1)、(V1,V2)、(V2,V3)、…、(Vn,V′),或者对有向图存在、、、…、,则称为顶点V到顶点V′的路径。记为PATH(V,V′)=(V,V1,V2,V3,…,Vn,V′)。路径长度：路径上含有的边或弧的个数。12345G1:1245G2:8回路或环(Cycle)：顶点V到顶点V的路径，即路径的第一个顶点和最后一个顶点相同的路径。简单回路：除第一个顶点和最后一个顶点之外，没有重复顶点的回路。简单路径：
6、除第一个顶点和最后一个顶点之外，没有重复顶点的路径。12345G1:1245G2:G1PATH(1,5):(1,2,3,5)√，(1,2,3,1,2,3,4,5)×。G2PATH(2,5):(2,4,1,5)√，(2,1,5,2,4,1,5)×。G1:(1,2,3,4,5,3,1)，(1,2,3,1)。G2:(1,5,2,4,1)，(1,5,2,4,5,2,1)。9连通图：任意两个不同顶点之间均有路径的图。对于有向的连通图，也称为强连通图。12345G1:1245G2:G1是连通的无向图；G2是连通
7、的有向图，也是强连通图。12345G:6798G1是不连通的无向图。10连通分量：无向图的极大连通子图。12345G:67981011121314G是不连通的无向图，它有3个连通分量。“极大”是指含有最多的边和最多的顶点，仍保持保持其连通性。12345123451234G的连通子图但不是连通分量的实例11生成树(树图)：连通的无向图的极小连通子图。“极小”是指含有最少的边(和最多的顶点)，仍保持保持其连通性。G是连通的无向图，它生成树如下。12345G:6798123456798123456798生
8、成树或树图与树的唯一区别是没有指定“根”。n个顶点的连通无向图的生成树，仅含有n-1个边。生成树不是唯一的。12生成森林：无向图的连通分量的极小连通子图(即连通分量的生成树)的集合。12345G:67981011121314G是生成森林如下。12345G:67981011121314显然，生成森林也是不唯一的。13网络：边上带有权的图。v1G:v2v3v4v5v61010201555816网络边上带有权，在实际应用中，可能表示各种成本值。如：顶点代表城市，边表示两城市
