第8章图.ppt
《第8章图.ppt》由会员分享,可在线阅读,更多相关《第8章图.ppt(34页珍藏版)》请在三一文库上搜索。
1、8.1 图的基本概念,第8章 图,8.2 图的存储结构,8.3 图的遍历,8.4 图的应用,最小生成树 拓扑排序,本章小结,关键路径 最短路径,问题1:n台计算机之间建立网络。 要求: n台计算机中的任何两台能通过网进行通信。 使总的代价最小。 问题2:邮递员送信的线路 (交通) 要求: 完成N个投递点的投递 总路径长度最短,8.1 图的基本概念 8.1.1 图的定义 (多对多) 图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合V(G),E是连接V中两个不同顶点的边的有限集合,记为E(G)。,图的分类,无向图: G=(V, E) V
2、(G)=v0,v1,v2,v3,v4 E(G)=(V1,V2), (V1,V3), (V1,V0), (V2,V3), (V2,V4), (V4,V3), (V4,V0), (V0,V3) 其中, (x,y)表示从X到Y的一条边 已知无向图有n个结点,求边e e=n*(n-1)/2,有向图: G=(V, E) V(G)=v0,v1,v2,v3,v4 E(G)=, , , , , , , 其中, 表示从X到Y得一条弧 已知有向图有n个结点,求边e e=n*(n-1),8.1.2 图的基本概念和术语 基本术语 顶点:图中数据元素 弧(边): 有向图:由顶点和弧构成的图 无向图:由顶点和边构成的图
3、完全图:无向图有n(n-1)/2条边 有向完全图:有向图有n(n-1)个弧 权:与图的边或弧相关的数值叫做权 网: 带权的图称为网,8.1.2 图的基本术语 1. 顶点的度、入度和出度 在无向图中,顶点所具有的边的数目称为该顶点的度。 在有向图中,以顶点vi为终点的弧的数目,称为该顶点的入度。以顶点vi为始点的弧的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。,2. 完全图:边或者弧达到最大的图 无向完全图:边数达到n*(n-1)/2 如图a:有4个顶点,边数为6 有向完全图:弧数达到n*(n-1) 如图b:有4个顶点,弧数为12,3. 路径和路径长度及简单路径 路径:在一个图
4、G=(V,E)中,从顶点vi到顶点vj的一条路径。 路径长度:是指一条路径上经过的边的数目。 简单路径:路径中不含相同顶点。例如,右图中,(v0,v2,v1)就是一条简单路径,其长度为2。,4. 回路或环 回路与环:首尾顶点相同的路径被称为回路或环。 简单回路或简单环:只有首尾顶点相同的路径被称为简单回路或简单环。 例如,右图中,(v0,v2,v1,v0)就是一条简单回路,其长度为3。,5. 权和网 图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图,也称作网。,例子:,路径:V1 V2 V3 V5 V6
5、 V3 长度:5 简单路径: V1 V2 V3 V5 回路: V1 V2 V3 V5 V6 V3 V1 简单回路:V3 V5 V6 V3,例子:,路径:V1 V2 V5 V7 V6 V5 V2 V3 长度:7 简单路径: V1 V2 V5 V7 V6 回路: V1 V2 V5 V7 V6 V5 V2 V1 简单回路:V1 V2 V3 V1,图的存储方法很多,但是目标是相同的。即不仅要存储图中各个顶点的数据信息,还要存储顶点与顶点之间的关系(边或弧)。 两种存储方法: 邻接矩阵(数组存储) 邻接表,8.2 图的存储结构,8.2 图的存储结构,8.2.1 邻接矩阵存储方法 邻接矩阵是一个(nn)阶
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章图
链接地址:https://www.31doc.com/p-2578696.html