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

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

1、数据结构-第七章图(图的定义存储实现和图的遍历)描述7.1.1图的定义若∈VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(Head)，或终端点。此时图中的弧是有方向的，此时的图称为有向图(Digraph)。若∈VR，必有∈VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边(Edge)，此时的图称为无向图(Undigraph)。7.1.1图的定义图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。图的抽象类型定义和基本操作如P156所示。7.1

2、.2图的基本术语图邻接点路径和回路度权与网生成树路径路径长度回路或环简单路径简单回路无向图有向图完全图子图连通图7.1.2图的基本术语无向图：若∈VR，必有∈VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边（Edge），此时的图称为无向图。ABCDE无向图G27.1.2图的基本术语若∈VR，则表示从顶点x到顶点y的弧(Arc)，称x为弧尾(Tail)或起始点，称y为弧头(Head)，或终端点（箭头指向的点）。图中的边是有方向的，此时的图称为有向图(Digraph)。ABCD有向图G17.1

3、.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图的基本术语完全图有向完全图：有n(n-1)条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。12347.1.2图的基本术语完全图无向完全图：有

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

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

6、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’相关联。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。有向图路径：

7、如果图G是有向图，则路径也是有向的，顶点序列应满足∈A，1≤j≤m。路径长度：指路径上经过的弧或边的数目。简单路径：若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。7.1.2图的基本术语回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v’，则称该路径为一个回路或环。简单回路（简单环）：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。7.1.2图的基本术语度无向图的度：顶点v的度是指和v相联的边的数目，记作TD(v)。有向图的度：对于有向图而言顶点v的度有出度和入度两部分：以顶点v为弧