《非线性数据结构h》PPT课件

《《非线性数据结构h》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.6非线性数据结构图2.6.1图及其基本概念图是一种较之线性表和树形结构更为复杂的非线性数据结构。如果数据元素集合D中的各数据元素之间存在任意的前后件关系，则此数据结构称为图。图中各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。图是对结点的前件和后件个数不加限制的数据结构。一、图（Graph）的定义图G=（V，E）其中：V={v1，v2，……,vn}是非空有穷的结点集合；E是顶点偶对的集合。例，图G1=（V，E）V={v1，v2，v3，v4}E={（v1，v2），（v1，v3），（v2，v1），（v2，v3），（v

2、2，v4），（v3，v1），（v3，v2），（v4，v2）}oooov1v2v3v4G1二、有向图、无向图有向图（Digraph）图G中顶点的偶对若是有向的，形成的图称为有向图，如图G2所示。为示区别，其偶对用表示。无向图（Undigraph）图G中顶点的偶对若是无向的，形成的图称为无向图，其偶对用（vx，vy）表示(区别在括号)，如图G1所示。G2=（V，E）V={1，2，3，4}E={〈1，2〉，〈1，3〉,〈3，4〉，〈4，1〉}1324G2三、边、弧边（Edge）顶点间的关系可描述为顶点的偶对，也称为顶点的

3、边。记为：（Vx，Vy）。边是无序的，可以看成是（Vx，Vy），也可以看成是（Vy，Vx）。弧（Arc）若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：〈Vx，Vy〉。弧是有序的，〈Vx，Vy〉表示从Vx到Vy。弧头（Head）弧的终点（TerminaLNode）称为弧头（方向前方）。弧尾（Tail）弧的起始点（InitialNode）称为弧尾（方向后方）。弧〈Vx，Vy〉表示为，弧尾弧头VxVy四、顶点、邻接点顶点（Vertex）:图中的数据元素（结点）称为顶点。如图G1、G2中的Ｖ1、Ｖ2，1，2。邻接点（Adjac

4、ent）无向图中，若边（Ｖx，Ｖy）E，则Ｖx、Ｖy互为邻接点。有向图中，若弧〈Ｖx，Ｖy〉E，则Ｖy是Ｖx的邻接点，反之，不是。(弧头是弧尾的邻接点)VxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx的邻接点1324G2oooov1v2v3v4G1五.顶点的度（Degree）在图中，一个结点的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度与出度之和称为该结点的度。对于无向图来说，其中每一个结点的入度等于该结点的出度。图中结点的最大度称为图的度。oooov1v2v3v4G11324G2六.路径、长度路径（P

5、ath）在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，…,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：（V1V2V3）或（V1V3）；而G2中，1到4的路径为<134>。长度（Length）路径的长度是该路径上边或弧的数目。例如，G1中V1到V3的长度为1或2；而G2中1到4的长度为2。1324G2oooov1v2v3v4G1图的应用实例[路径问题]城市中有许多街道，每一个十字路口都可以看作图中的一个顶点，邻接两个十字路口之间的每一段街道既可以看作一条，也可以看作两条有向

6、边。如果街道是双向的，就用两条有向边。如果街道是单向的，就用一条有向边。(路线咨询)2.6.2、图的存储结构根据图的定义可知，图的逻辑结构分为两部分：V（顶点）和E（边或弧）的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为关联矩阵。关联矩阵也称为邻接矩阵。1、关联矩阵表示法关联矩阵定义在关联矩阵R中，每一个元素R(i,j)的定义为1di是dj的前件R(i，j)=0di不是dj的前件例如G2的关联矩阵为：0110101111000100R=4x4注意：一定对称，对角线

7、全为0注意：不一定对称，对角线不一定为0oooov1v2v3v4G11324G20110000000011000R=4x4G1的关联矩阵为：2、求值矩阵关联矩阵只表示了图的结构，即图中各结点的前后件关系。但在许多实际问题中，还需要对两个关联结点之间的值进行运算。这就是说，除了要存储图中各结点值以及各结点之间的关系外，还必须存储图中每两个结点之间的求值函数。为了表示有值图中每两个结点之间的求值函数，可以另外用一个求值矩阵V来存储。例3、邻接表表示法datalink指向dk单链表的第一个结点存放dk信息邻接表这种存储结构也称为“顺序

8、-索引-链接”存储结构。用一个顺序存储空间来存储图中各结点的信息。数据域data与指针域link。数据域存放图中编号为k的结点值；指针域link用于链接相应结点的后件，对于图中每一个结点，构造一个单链表。该单链表的头指针即为顺序空间中的对应存储结点的指针域。单链