图的定义和术语图的存储结构图的遍历与连通性最小生成树活及应用探究.ppt

图的定义和术语 图的存储结构 图的遍历与连通性 最小生成树 活动网络 最短路径 7.1 图的定义和术语 图形结构的形式定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, R ) 其中： V = { x | x ? 某个数据对象} ， 是顶点的有穷非空集合； R——边的有限集合 R = {(x, y) | x, y ? V } 无向图 或 R = {x, y | x, y ? V Path (x, y)}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头 有向图与无向图 有向图中：边用x, y表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 在具有n 个顶点的有向图中，最大弧数为 n(n-1) 在具有n 个顶点的无向图中，最大边数为 n(n-1)/2 顶点的度 无向图：与该顶点相关的边的数目 有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目 在有向图中, 顶点的度等于该顶点的入度与出度之和。 邻接点 无向图：两顶点之间有条边，则两顶点互为邻接点 x —— y ( x ,y ) 有向图：从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点 x y x ,y 权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’? V 且 E‘?E, 则称 图G’ 是 图G 的子图。 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和。 简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 生成树是对指连通图来而言的 是连同图的极小连同子图 包含图中的所有顶点 有且仅有n-1条边 本章不予 讨论的图 7.2 图的存储表示 顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。 设图 G = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵G.arcs[n][n] 定义为： G.arcs[i][j]= 1 若Vi,Vj 或(Vi,Vj)∈E 0 反之 无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。 网的邻接矩阵 邻接表 (Adjacency List)—— 一种链式存储结构 把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代