1、 数据结构(DATA STRUCTURE)计算机 科学与技术学院*课程代码： 0600060第七章 图n 图的基本概念图的基本概念 n 图的存储表示图的存储表示 n 图的遍历与连通性图的遍历与连通性 n 最小生成树最小生成树 n 最短路径最短路径 n 活动网络活动网络2*课程代码： 06000607.1 图的基本概念图的基本概念n 图的定义 图是由顶点集合图是由顶点集合 (vertex)及顶点间及顶点间的关系集合组成的一种数据结构的关系集合组成的一种数据结构 ：Graph ( V, E ) 其中其中 V = x | x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E
2、= (x, y) | x, y V 或或 E = | x, y V 顶点顶点 v 的出度的出度 是以是以 v 为始点为始点 (弧尾弧尾 )的有向边的条数的有向边的条数 , 记作记作 OD(v)。n 路径路径 在图在图 G (V, E) 中中 , 若从顶点若从顶点 vi 出发出发 , 沿一些沿一些边经过一些顶点边经过一些顶点 vp1, vp2, , vpm， 到达顶点到达顶点 vj。 则称则称顶点序列顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点为从顶点 vi 到顶点到顶点 vj 的路径的路径 。它经过的边。它经过的边 (vi, vp1)、 (vp1, vp2)、 .、 (v
3、pm, vj)应是属于应是属于 E 的边。的边。6*课程代码： 0600060n 路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。n 简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不互相均不互相重复重复 , 则称这样的路径为简单路径。则称这样的路径为简单路径。n 回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶点与最后一个顶点 vm 重合重合 , 则称这样的路径为回路或环。则称这样的路径为回路或环。n 简单回路简单回路
4、除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路 7*课程代码： 0600060例1 5 73 2 4G26例2 4 51 3 6G1路径： 1， 2， 3， 5， 6， 3路径长度： 5简单路径： 1， 2， 3， 5回路： 1， 2， 3， 5， 6， 3， 1简单回路： 3， 5， 6， 3路径： 1， 2， 5， 7， 6， 5， 2， 3路径长度： 7简单路径： 1， 2， 5， 7， 6回路： 1， 2， 5， 7， 6， 5， 2， 1简单回路： 1， 2， 3， 18*课程代码： 06000607.2 图的存储结构图的存储结构1）存储特点）存储特点 在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个 记录各个记录各个顶点信息顶点信息 的的 顶点表；顶点表； 还有一个还有一个 表示各个顶点之间关系表示各个顶点之间关系 的的 邻接矩邻接矩阵阵 。2）邻接矩阵）邻接矩阵 设图设图 A = (V, E)是一个有是一个有 n 个顶点的图，则个顶点的图，则图的图的 邻接矩阵邻接矩阵 是一个二维数组是一个二维数组 Ann， 定义：定义：7.2.1 邻接矩阵邻接矩阵 (Adjacency Matrix)表示法表示法9*课程代码： 0600060 10
