数据结构-第七章图(图的定义存储实现和图的遍历)描述.ppt

《数据结构-第七章图(图的定义存储实现和图的遍历)描述.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径第七章图7.1.1图的定义7.1.2图的基本术语7.2.1邻接矩阵表示7.2.2邻接表表示7.1.1图的定义图（Graph）是一种网状数据结构，其形式化定义如下：Graph=(V,R)V={x

2、x∈DataObject}R={VR}//数据关系VR={

3、P(x,y)∧(x,y∈V)}DataObject：是一个集合，该集合中的所有元素具有相同的特性。V：中的数据元素通常称为顶点（Vertex）（图中的顶点）

4、。VR：是两个顶点之间的关系的集合。P(x,y)：表示x和y之间有特定的关联属性P。7.1.1图的定义若∈VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(Head)，或终端点。此时图中的弧是有方向的，此时的图称为有向图(Digraph)。若∈VR，必有∈VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边(Edge)，此时的图称为无向图(Undigraph)。7.1.1图的定义图的基本操作和其它数据结构一样，也

5、有创建、插入、删除、查找等。图的抽象类型定义和基本操作如P156所示。7.1.2图的基本术语图邻接点路径和回路度权与网生成树路径路径长度回路或环简单路径简单回路无向图有向图完全图子图连通图7.1.2图的基本术语无向图：若∈VR，必有∈VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边（Edge），此时的图称为无向图。ABCDE无向图G27.1.2图的基本术语若∈VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(

6、Head)，或终端点（箭头指向的点）。图中的边是有方向的，此时的图称为有向图(Digraph)。ABCD有向图G17.1.2图的基本术语ABCDABCDE有向图G1无向图G2结点(顶点)有向边（弧）、弧尾(初始结点)、弧头(终止结点)ABAB有向图：G1=(V1，E1)V1={A,B,C,D}E1={,,,}结点(顶点)边(无向边)AB无向图：G2=(V2，E2)V2={A,B,C,D,E}E2={(A,B),(A,C),(B,D),(B,E）,(C,E),(D,E)}AB7.1.2

7、图的基本术语完全图有向完全图：有n(n-1)条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。12347.1.2图的基本术语完全图无向完全图：有n(n-1)/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为无向完全图（或称为完全图）。1234注意：对于有很少条边的图（e

8、BCDEABDEAABCDABCDE无向图G2的子图有向图G17.1.2图的基本术语连通图：在无向图G=(V,{E})中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vj∈V，vi,vj都是连通的，则称该无向图G为连通图。7.1.2图的基本术语连通分量：无向图中的极大连通子图称为该无向图的连通分量。ABCDEFGIJLHMKABCDEHMFGIJLK无向图G无向图G的三个连通分量7.1.2图的基本术语强连通图：在有向图G=(V,{A})中，若对于每对顶点vi、vj∈V且vi≠vj，

9、从vi到vj和vj到vi都有路径，则称该有向图为强连通图。7.1.2图的基本术语强连通分量：有向图的极大强连通子图称作有向图的强连通分量。有向图G有向图G的两个强连通分量ABCDABCD7.1.2图的基本术语邻接点对于无向图G=(V,{E})，如果边(v,v’)∈E，则称顶点v,v’互为邻接点，即v,v’相邻接。边（v,v’）依附于顶点v和v’，或者说边（v,v’）与顶点v和v’相关联。对于有向图G=(V,{A})而言，若弧∈A，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v，或者说弧与顶点v,v’

10、相关联。7.1.2图的基本术语路径和回路路径路径长度回路或环简单路径简单回路7.1.2图的基本术语路径无向图路径：无向图G=(V,{E})中从顶点v到v’的路径是一个顶点序列（v=vi,0,vi,1,vi,2,...,vi,m=v’)，其中(vi,j-1,vi,j)∈E,1≤j≤m。有向图路径：如果图G