第八章 图 .ppt
《第八章 图 .ppt》由会员分享,可在线阅读,更多相关《第八章 图 .ppt(133页珍藏版)》请在文库网上搜索。
1、第八章 图 图的基本概念 图的存储结构 图的遍历与连通性 最小生成树 最短路径 活动网络1图的基本概念 图定义 图是由顶点(vertex)集合以及顶点之间的关系集合组成的一种数据结构:G( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合;E = (x, y) | x, y V 或 E = | x, y V 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 outdeg(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。 路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过若干顶点 vp1, vp2, , vpm,到达顶点vj,则称顶点序
2、列 (vi , vp1 , vp2 , . , vpm , vj) 为从顶点vi 到顶点 vj 的一条路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 都是 于E的边。5 路径 度 非带权图的路径 度是 此路径边的条数。带权图的路径 度是 路径 边的权值之和。 单路径 若路径 顶点 v1, v2, ., vm 互相重 , 则称 的路径为 单路径。 路 若路径 第一个顶点 v1 与最 一个顶点vm 重合, 则称 的路径为 路或 。601 2301 2301 23 连通图与连通 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中 一对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八