数据结构之图的存储结构与遍历.ppt

《数据结构之图的存储结构与遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第7章图7.1图的定义与基本术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图的应用7.6最短路径返回主目录图结构与表结构和树结构的不同表现在结点之间的关系上，线性表中结点之间的关系是一对一的；树是按分层关系组织的结构，树结构之间是一对多；对于图结构，图中顶点之间的关系可以是多对多，即一顶点和其它顶点间的关系是任意的，可以有关也可以无关。因此，图G树TL，图是一种比较复杂的非线性数据结构。图作为一种非线性结构，被广泛应用于多个技术领域。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以

2、及如何利用图来解决一些实际问题。返回主目录7.1图的定义与基本术语7.1.1图的定义图（Graph）是一种网状数据结构，其形式化定义如下：Graph=（V，R）V={x∣x∈DataObject}R={VR}VR={∣P（x，y）∧（x，y∈V）}返回主目录DataObject为一个集合，该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点（vertex），VR是两个顶点之间的关系的集合。P（x，y）表示x和y之间有特定的关联属性P。弧：若∈VR，则表示从顶点x到顶点y的一条弧（arc），并称

3、x为弧尾（tail）或起始点，称y为弧头（head）或终端点。有向图：若图中的边是有方向的，称这样的图为有向图。返回主目录无向图：若∈VR，必有∈VR，即VR是对称关系，这时以无序对（x，y）来代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图。例如：下图G1是有向图，G2是无向图2134G12145G23返回主目录在图中，我们可以将任一顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之间也不存在顺序关系。为了操作的方便，我们需要将图中的顶点按任意序列排列起来。顶点在这个人为的随

4、意排列中的位置序号称为顶点在图中的位置。图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。返回主目录图的抽象类型定义：ADTGraph数据对象V：一个集合，该集合中的所有元素具有相同的特性。数据关系R：R={VR}VR={∣P（x，y）∧（x，y∈V）}返回主目录基本操作：（1）GreateGraph(G)：创建图G。（2）DestoryGraph(G)：销毁图G。（3）LocateVertex(G,v)：确定顶点v在图G中的位置。若图G中没有顶点v，则函数值为“空”。（4）GetVertex(G,I)：取出

5、图G中的第i个顶点的值。若i>图G中顶点数，则函数值为“空”。返回主目录（5）FirstAdjVertex(G,v)：求图G中顶点v的第一个邻接点。若v无邻接点或图G中无顶点v，则函数值为“空”。（6）NextAdjVertex(G,v,w)：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟在w后面）。若w是v的最后一个邻接点，则函数值为“空”。（7）InsertVertex(G,u)：在图G中增加一个顶点u。返回主目录（8）DeleteVertex（G，v）：删除图G的顶点v及与顶点v相关联的弧。（9）Insert

6、Arc（G，v，w）：在图G中增加一条从顶点v到顶点w的弧。（10）DeleteArc（G，v，w）：删除图G中从顶点v到顶点w的弧。（11）TraverseGraph（G）：按照某种次序，对图G的每个结点访问一次且最多一次。返回主目录7.1.2基本术语设用n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。无向完全图：有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为无向完全图。有向完全图：有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完

7、全图。返回主目录稀疏图：对于有很少条边的图（e∈A，则称顶点v邻接到顶点v/，顶点v/邻接自顶点v，或者

8、说弧与顶点v，v/相关联。邻接点：返回主目录度、入度和出度对于无向图而言，顶点v的度是指和v相关联的边的数目，记作TD（v）。对于有向图而言，顶点v的度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度，记作ID（v），以顶点