资源描述：
《北航数据结构课件 (8)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章第八章图图图一个数据元素----顶点A数据元素(顶点)之间的关系----边(弧)BBABABAA本章讨论的主要内容本章讨8.1图的基本概念8.2图的存储方法8.3图的遍历8.4最小生成树应用8.5最短路径问题8.6AOV网与拓扑排序8.7AOE网与关键路径重点8.1图的基本概念一.图的定义图是由顶点的非空有穷集合与顶点之间关系(边或弧)的集合构成的结构,通常表示为G=(V,E)其中,V为顶点集合,E为关系(边或弧)的集合。非空有穷集合关于一条边或弧的表示vivjvivj(1)用图形vjvjvivi(2)用符号(v,v)或ijij顶点偶对
2、(3)用语言顶点v与v是这条边的两个邻接点。ij这条边依附于顶点v和顶点v。ijv1v例例1v2v3vv32v4v4G1=(V1,E1)G2=(V2,E2)其中其中V1={v1,v2,v3,v4}V2={v1,v2,v3,v4}E1={(v1,v2),(v1,v3),E2={,,(v1,v4),(v2,v3),,}(v2,v4),(v3,v4)}二.图的分类无向图对于（vi,vj)ÎE,必有（vj,vi)ÎE，并且偶对中顶点的前后顺序无关。有向图若ÎE是顶点的有序偶对。网(络)与边有
3、关的数据称为权,边上带权的图称为网络。v1v10v114v17v23vvv2v3238v4v4v4无向图有向图网(络)三.名词术语1.顶点的度依附于顶点vi的边的数目,记为TD(vi)。对于有向图而言,有:顶点的出度:以顶点vi为出发点的边的数目,记为OD(vi)。顶点的入度:以顶点vi为终止点的边的数目,记为ID(vi)。TD(vi)=OD(vi)+ID(vi)v1v1vv32vv23v4v4对于具有n个顶点,e条边的图,有结论1n1e=2åTD(vi)i=1结论2具有n个顶点的无向图最多有n(n-1)/2条边。结论3具有n个顶点的有向图最多有n(n
4、-1)条边。边的数目达到最大的图称为完全图。边的数目达到或接近最大的图称为稠密图，否则,称为稀疏图。(v,v),(v,v),¼,(v,v)或2.路径和路径长度xi1i1i2imy都在E中,,¼,xi1i1i2imy顶点vx到vy之间有路径P(vx,vy)的充分必要条件为:存在顶点序列vx,vi1,vi2,…,vim,vy,并且序列中相邻两个顶点构成的顶点偶对分别为图中的一条边。BAEP(A,E):A,B,E(第1条路径)A,C,D,E(第2条路径)CD出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为
5、简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权图的路径长度是指路径上经过的边上的权值之和。3.子图对于图G=(V,E)与G´=(V´,E´),若有V´ÍV,E´ÍE,则称G´为G的一个子图。v1v1v1v2v3v2v3v2v4v4G´2GG´14.图的连通(1)无向图的连通无向图中顶点vi到vj有路径,则称顶点vi与vj是连通的。若无向图中任意两个顶点都连通,则称该无向图是连通的。连通分量——无向图中的极大连通子图。v1v1v6v1v6v7v7v9v2vv93vvv23vv23v55v4v4v4连通图非连通图2个连通分量(2)有向图的连
6、通若有向图中顶点vi到vj有路径,并且顶点vj到vi也有路径，则称顶点vi与vj是连通的。若有向图中任意两个顶点都连通，则称该有向图是强连通的。强连通分量——有向图中的极大强连通子图。v1v1v2v3v2v3v2v3v4v4v4(强)连通图非连通图强连通分量5.生成树包含具有n个顶点的连通图G的全部n个顶点,仅包含其n-1条边的极小连通子图称为G的一个生成树。vv1v11v1vvv3v2v3v232vv32vvv444G的生成树v4v1v1Gv2v3vv3…2v4v4本章不讨论的图1.带自身环的图2.多重图v1v1v2v2vv3v438.2图的存储方法
7、对于一个图对于一个图,,需要需要存储的存储的信息应该信息应该包括包括::(1)所有顶点的数据信息；(2)顶点之间关系(边或弧)的信息;(3)权的信息(对于网络)。“第i个顶点”“顶点i”一.邻接矩阵存储方法数组存储方法·顶点信息核心思想:采用两个数组存储一个图。·边或弧的信息·权1.定义一个一维数组VERTEX[0..n-1]存放图中所有顶点的数据信息(若顶点信息为1,2,3,¼,此数组可略)。2.定义一个二维数组A[0..n-1,0..n-1]存放图中所有顶点之间关系的信息(该数组被称为邻接矩阵),有1当顶点vi到顶点vj有边时A[i][j]={0当
8、顶点vi到顶点vj无边时对于带权的图,有wij当顶点vi到vj有边,且边的权为wijA[i][
