数据结构第7章 图课件.ppt

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

1、对比线性结构、树形结构和图状结构的特点在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继（一个对一个）；在树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关（一个对多个）；在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关（多个对多个）。1其中：V={ei

2、ei∈ElemSet,i=1,2,…,n}R={VR}VR={

3、v,w∈V且P(v,w)}谓词P(v,w)定义了之间关系的意义或信息。7.1图的类型定义图是由一个顶点集V和一个关系集R构成的数据结

4、构。Graph=(V,R)2若VR，则表示从v到w的一条弧，v称为弧尾，w称为弧头。弧：由顶点集和弧集构成的图。有向图：例如:G1=(V1,{VR1})其中V1={A,B,C,D,E}，VR1={,,,,,}基本术语13G2=(V2,{VR2})其中V2={A,B,C,D,E}，VR2={(A,B),(A,C),(B,C),(B,E),(C,D),(D,E)}若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。边：由顶点集和边集构成的图。无向图：例如:基本术语24边或者弧带权的图

5、。网：设图G=(V,{VR})和图G=(V,{VR})，且VV,VRVR,则称G为G的子图。子图：基本术语35子图：6假设图中有n个顶点，则含有n(n-1)/2条边的无向图。完全图：含有n(n-1)条弧的有向图。有向完全图：边或弧的个数e

6、联的边/弧的数目，记为TD(v)。对于有向图，TD(v)=ID(v)+OD(v)对于有向图(V,{VR})，如果VR，则称顶点v邻接到顶点w，顶点w邻接自顶点v，弧和顶点v,w相关联。基本术语58例：有向图的度、入度、出度245136顶点2的度TD(2)=4，其中，入度ID(2)=1，出度OD(2)=3。顶点4的度TD(4)=1，其中，入度ID(4)=1，出度OD(4)=0。91573246顶点1的度：顶点2的度：顶点3的度：顶点4的度：顶点5的度：顶点6的度：顶点7的度：TD(1)=2TD(2)=4TD(3)=2TD(4)=1TD(5)=3TD(6)=1TD(7)=1总

7、边数为：7一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边/弧的图，满足下列关系：10一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边/弧的图，满足下列关系：ID(A)=1,OD(A)=2,TD(A)=3ID(B)=1,OD(B)=1,TD(B)=2ID(C)=1,OD(C)=2,TD(C)=3ID(D)=2,OD(D)=2,TD(D)=4ID(E)=2,OD(E)=0,TD(E)=2A:B:C:D:E:总弧数为：711路径：图(V,{VR})中的一个顶点序列{v=vi,0,vi,1,…,vi,m=w}，(vi,j-1,vi,j)VR或者

8、,vi,j>VR，1≤j≤m。路径长度：路径上边/弧的数目。序列中顶点不重复出现的路径。简单路径：序列中第一个顶点和最后一个顶点相同的路径。回路/环：从A到C的路径为{A,D,B,C}路径长度为3。除第一个顶点和最后一个顶点之外，其余顶点不重复的回路。简单回路/环：121，2，3；1，2，3，5，6，3；1，2，3；1，2，3，1；3，5，6，3；1，2，3，5，6，3，1；1，2，11，2，3，1；3，5，6，3；1，2，1顶点1到顶点3的路径：其路径长度为：简单路径：回路（环）：简单回路：有向图G12451365213对于无向图，如果图中任意两个顶点之间都有路径相通，则称其为连通图。连通

9、图：非连通图的每一个连通部分称为连通分量。连通分量：连通：在无向图中，如果从顶点v到顶点w有路径，则称v和w是连通的。V0V4V3V1V2图G1V0V2V3V1V5V4图G2V0V2V3V1G2的连通分量连通图非连通图14无向图G3：LABMCFIDGJEHK无向图G3的3个连通分量：DEIGHKLABMCFJ非连通图15强连通图：对于有向图，若任意两个顶点之间都存在路径，则称其为强连通图。强连通