《图的定义和术语》PPT课件

《《图的定义和术语》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图图(Graph)是一种较线性表和树更为复杂的数据结构.在线性表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关;而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学逻辑学物理化学电讯工程计算机科学以及数学的其他分支中.7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图

2、的连通性问题7.5有向无环图及其应用7.6最短路径￡7.1图的定义和术语（1）形式化定义Graph=(V,R)V={x

3、x∈dataobject}//顶点的有穷非空集合R={VR}VR={

4、P(v,w)∩(v,w∈V)}//两个顶点之间的关系集合（2）图形表示图7.1图的示例(b)无向图G2G1V1V2V3V4(a)有向图G1图由结点及边(弧)组成,与树的主要区别在于图可以有回路V3V4V5V1V2G2(a)有向图G1G1＝(V1,{A1})其中：V1={v1,v2,v3,v4}A1={,,,}(

5、b)无向图G2G2＝(V2,{E2})其中：V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}（3）相关术语顶点（Vertex）：图中的数据元素。弧（Arc）：若∈VR，则表示从v到w的一条弧。弧尾（Tail）或初始点（Initialnode）：弧的一个顶点v。弧头（Head）或终端点（Terminalnode）：弧的一个顶点w。有向图（Digraph）：由弧和顶点组成。边（Edge）：若∈VR必有∈VR，即VR

6、是对称的，则以无序对(v,w)代替这两个有序对，表示v和w之间的一条边。无向图（Undigraph）：由边和顶点组成。若，用n表示图中顶点数目，用e表示边或弧的数目。且不考虑顶点到其自身的边或弧，即若∈VR，则vi≠vj。那么，；对于无向图，e的对于有向图，e的取值范围是0到取值范围是0到n(n－1)。无向完全图（Completedgraph）：有条边的无向图。有向完全图：有n(n－1)条弧的有向图。稀疏图（Sparsegraph）：有很少条边或弧（如e

7、=(V,{E})和G’=(V’,{E’})，如果V’V且E’则称G’为G的子图。E,(a)图7.1中G1的子图V1V4V1V1V1V2V4V3V3V3(b)图7.1中G2的子图图7.2子图示例V1V4V1V2V4V5V3V3V1V2V1V2V4V5对于无向图G=(V,{E})，如果边(v,v’)∈E，则称顶点v和v’互为邻接点（Adjacent）。边(v,v’)依附（Incident）于顶点v和v’，或者说(v,v’)和顶点v和v’相关联。度：指和顶点v相关联的边的数目，记为TD(v)。对于有向图G=(V,{A})，如果弧∈A，则称顶点v邻接到顶点v

8、’，顶点v’邻接自顶点v。弧和顶点v、v’相关联。入度（InDegree）：以顶点v为头的弧的数目，记为ID(v)。出度（OutDegree）：以顶点v为尾的弧的数目，记为OD(v)。有向图中，顶点v的度为TD(v)＝ID(v)＋OD(v)。一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边或弧的图，满足如下关系：路径（Path）：在无向图G=(V,{E})中从顶点v到顶点v’的一个顶点序列(v=vi,0,vi,1,…,vi,m=v’)，其中(vi,j-1,vi,j)∈E，1≤j≤m。若G是有向图，则路径也是有向的，顶点序列满足

9、i,j-1,vi,j>∈E，1≤j≤m。路径的长度：路径上的边或弧的数目。简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。回路或环（Cycle）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。连通：在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。连通图（ConnectedGraph）：对于图中任意两个顶点vi,vj∈V，vi和vj都是连通的图。连通分量（ConnectedComponent）：指无向图中的极大连通子图。(a)无向图G3(b)G3的3个连通分量图7.3无向图及其连通分量DE

10、G3ABCDEFGHIK