chap7第七章 图.ppt

图的基本概念 图的存储结构 图的遍历 图的连通性问题 最小生成树 最短路径 活动网络 图的基本概念 图定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E1 = {(x, y) | x, y ? V } 或 E2 = {x, y | x, y ? V Path (x, y)} 其中， E1是顶点之间关系的有穷集合，也叫做边(edge)集合，此时的图称为无向图。 E2 表示从 x 到 y 的一条弧，且称x为弧尾，y为弧头，这样的图称为有向图。 例 G1=V1,E1 V1={v1,v2,v3,v4 ,v5 } E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)} 例 G2=V2,E2 V2={v1,v2,v3,v4 } E2={v1,v2, v1,v3, v3,v4 , v4,v1} 图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 图的基本术语 有向图与无向图 在有向图中，顶点对 x, y 是有序的。在无向图中，顶点对(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为无向完全图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为有向完全图。 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。（邻接点：边的两个顶点）关联边：若边e= (v, u),则称边e和顶点v、u相关联 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’? V 且 E‘?E, 则称 图G’ 是 图G 的子图。 权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。 顶点的度 一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)。 路径 在图 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条边的图必定是生成树吗？ 对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edge[n][n]，定义(满足如下条件的n阶矩阵)： 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。 网络的邻接矩阵 用邻接矩阵表示的结构定义 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。 邻接表 (Adjacency List) 邻接表:是图的一种链式存储结构。 弧的结点结构 adjvex; // 该弧所指向的顶点的位置 nextarc;// 指向下一条弧指针 info;