数据结构第5章刘震

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

1、2021/7/16第五章图论与贪心算法主讲老师：刘震$5.1图—图的基本概念图是常用的重要的一类数据结构，上一章的树可以看成是图的特例，树中每个数据元素至多允许一个前驱，只能反映数据元素之间一对多的关系，而图中没有该限制，允许数据元素可以有多个前驱，因此可以反映数据元素之间多对多的关系。$5.1图—图的基本概念1有向图无向图$4.1图—图的基本概念1有向图G=（V，{A}）其中，V为顶点的有穷非空集合{A}为顶点之间的关系集合G1=（V，{A}）V={v1,v2,v3,v4}A={,,,}其中表示从x到

2、y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)①②③④G1$5.1图—图的基本概念1无向图G=（V，{E}）其中,V同有向图，{E}为顶点之间的关系集合，E为边集合G2=（V，{A}）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v4),v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x与y之间的一条连线，称为边（edge）①②G2③④⑤$5.1图—图的基本概念1图的顶点数为n,边数为e,请找出n与e的关系设n为顶点数，e为边或弧的条数对无向图有：0<=e<=n(n-1)/2有向图有：

3、0<=e<=n(n-1)$5.1图—图的基本概念2完全图:边达到最大的图无向完全图：边数为n(n-1)/2的无向图有向完全图：弧数为n(n-1)的有向图权：与图的边或弧相关的数网：边或弧上带有权值的图$5.1图—图的基本概念3顶点的度TD（V）无向图：为依附于顶点V的边数有向图：等于以顶点V为弧头的弧数（称为V的入度，记为ID（V））与以顶点V为弧尾的弧的出度，记为OD（V））之和。即：TD（V）=ID（V）+OD（V）无向图e=1/2（∑TD(vi)）i=1结论：有向图nne=∑ID(vi)=∑OD(vi)i=1i=1无向图的度数为依附于顶点v的边数；有向图的度数等

4、于以顶点v为弧头的弧数与以顶点v为弧尾的弧数之和$5.1图—图的基本概念4-路径无向图：顶点v到v’的路径是一个顶点序列（v=vi0,vi1,…,vim=v’）其中，（vij-1,vij）∈E,1<=j<=m有向图：顶点v到v’的路径是有向的顶点序列（v=vi0,vi1,…,vim=v’）其中，∈A,1<=j<=m几个概念：路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即：（v=vi0,vi1,…,vim=v’=v）简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路$5.1图—图的基本概念

5、5-连通顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的连通图：包括无向连通图和有向连通图无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj)有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vi<>vj)连通分量：无向图：无向图中极大连通子图，称为连通分量有向图：有向图中极大强连通子图，称为强连通分量①②③④G1有两个强连通分量①②③④G1$5.1图—图的基本概念5-连通定义：设无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点，且只有n-1条边的连通子图三要素：n

6、个顶点n-1条边连通生成树n-1条边$5.1图—图的基本概念6-生成树$5.1图—图的基本概念7-子图子图是图的一部分，它本身也是一个图。如果有图G=(V，E)和G′=(V′,E′)，且V′是V的子集，E′是E的子集，则称G′是G的子图。图4-1实际上是中国铁路交通图的一个子图。$5.1图—图的基本概念8-邻接顶点邻接顶点在无向图中，若两个顶点之间有边连接，则这两个顶点互为邻接顶点$4.2图—图的存储回忆:天然气管道铺设问题中,需要存储社区房屋和商店信息,相互之间是否有通路及管道长度三个信息.即使部分问题不牵涉管道长度(图的权值),也至少需要存储图的顶点和边的两方面信

7、息,如何存储?仍然有顺序存储和链式存储2种方法!$4.2图—图的存储1-邻接矩阵一、数组表示法（邻接矩阵）设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：例如：G1、G2的邻接矩阵邻接矩阵的特点：1.判定两个顶点Vi与Vj是否关联,只需判A[i,j]是否为1；2.求顶点的度容易:有向图中：TD(Vi)=OD(Vi)+ID(Vi)nn=∑A[i,j]+∑A[j,i]j=1j=1nn无向图中：TD(Vi)=∑A[i,j]=∑A[j,i]j=1j=1即顶点Vi的度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数）。即顶点Vi