数据结构ppt教学课件第7章图

《数据结构ppt教学课件第7章图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1图的基本概念和术语7.2图的存储结构7.3图的遍历和求图的连通分量7.4图的生成树7.5最短路径7.6有向无环图及应用7.7图的第7章图返回主目录第7章图7.1图的基本概念和术语7.1.1图的基本概念图G由集合V和E组成,记为G=(V,E),图中的结点又称为顶点,其中V是顶点的非空有穷集合,相关的顶点的偶对称为边,E是边的有穷集合。若图中的边是顶点的有序对,则称此图为有向图。有向边又称为弧,通常用尖括弧表示一条有向边,〈vi,vj〉表示从顶点vi到vj的一段弧,vi称为边的始点(或尾顶点),vj称为边的终点

2、(或头顶点),〈vi,vj〉和〈vj,vi〉代表两条不同的弧。若图中的边是顶点的无序对,则称此图为无向图。通常用圆括号表示无向边,(vi,vj)表示顶点vi和vj间相连的边。在无向图中(vi,vj)和(vi,vj)表示同一条边,如果顶点vi、vj之间有边(vi,vj),则vi、vj互称为邻接点。图7.1给出两个图G1和G2,其中G1是无向图,G2是有向图。在有向图中用箭头表示弧的方向,箭头从始点指向终点。图G1是一个无向图的例子。在图G1中,V={v1,v2,v3,v4},E={(v1,v2),(v2,v3)

3、,(v1,v3),(v1,v4),(v3,v4)}。而(v2,v1)与（v1,v2）表示同一条边,(v2,v3)与(v3,v2)也表示同一条边,等。图G2是一个有向图的例子,在图G2中V={v1,v2,v3,},E={〈v1,v2〉,〈v1,v3〉,〈v2,v3,〉,〈v3,v2〉}。而〈v3,v2〉与〈v2,v3,〉表示两条不同的边。对于图G=(V,E),G′=(V′,E′),若有V′∈V,E′∈E,则称图G′是G的一个子图。图7.2给出了G3与其子图G3′。在下面的讨论中不考虑顶点到自身的边,也不允许

4、一条边(或弧)在图中重复出现。因此有n个顶点的无向图最大边数为C2n=n(n-1)/2,这样的图称为无向完全图；有向图中最多可能有A2n=n(n-1)条弧,这样的图称为有向完全图。7.1.2路径和回路所谓顶点vp到顶点vq之间的路径,是指顶点序列vp,vi1,vi2,…,vim,vq,其中（vp,vi1）,（vi1,vi2）,…,（vim,vq）分别为图中的边。路径上边的数目称为路径长度。图7.3所示的无向图中,顶点v1(注：v1在图中用数字1表示，其余类同)到顶点v5的路径有两条,分别为v1,v2,v3,

5、v4与v1,v5,v4,路径长度分别为3和2。如果路径的起点和终点相同(即vp=vq),则称此路径为回路或环。序列中顶点不重复出现的路径称为简单路径,图7.3所示的v1到v5的两条路径都为简单路径。除第一顶点与最后一个顶点之外,其它顶点不重复出现的回路为简单回路或者简单环。7.1.3连通图若从顶点vi到顶点vj(i≠j)有路径,则vi和vj是连通的。如果无向图中任意两个顶点vi和vj都是连通的,则称无向图是连通的。无向图中极大连通子图称为连通分量。图7.2中的G3有两个连通分量,见图7.4(a)。对于有向图来

6、说,图中任意一对顶点vi和vj(i≠j)均有从vi到vj及从vj到vi的有向路径,则称该有向图是强连通的。有向图中的极大强连通子图称为该有向图的强连通分量。图7.1中G2不是强连通的,但它有一个强连通分量,见图7.4(b)。7.1.4顶点的度顶点的度是指依附于某顶点vi的边数,通常记为TD(vi)。在有向图中,要区别顶点的入度和出度的概念。所谓顶点vi的入度是指以vi为终点的弧的数目,记为ID(vi);所谓顶点vi的出度是指以vi为始点的弧的数目,记为OD(vi)。显然TD(vi)=ID(vi)+OD(vi)

7、例如,在G1中顶点v1的度TD(v1)=3,在G2中顶点v2的入度ID(v2)=2,出度OD(v2)=1,TD(v2)=3。可以证明,对于具有n个顶点、e条边的图,顶点vi的度TD(vi)与顶点的个数及边的数目满足关系:7.2图的存储结构7.2.1邻接矩阵图的邻接矩阵表示法是用一个二维数组来表示图中顶点之间的相邻关系。设图G=(V,E)有n(n≥1)个顶点,则G的邻接矩阵是按如下定义的n阶方阵:aij=1若(vi,vj)或∈E(G)0反之例如,图7.1中的G1、G2的邻接矩阵分别

8、表示为A1和A2,矩阵的行、列号对应于图中结点的号。从图的邻接矩阵表示法中很容易看出图的一些特性,这种表示方法具有以下特点:(1)无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵;对有n个顶点的无向图则只需存入上(下)三角形,故只需n(n+1)/2个