《2013-26非线性数据结构(2h).ppt》由会员分享，可在线阅读，更多相关《2013-26非线性数据结构(2h).ppt（36页珍藏版）》请在三一文库上搜索。
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）， （v2，v4），（v3，v1）， （v3，
2、v2），（v4，v2）,二、有向图、无向图,有向图（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,三、 边、弧,边（Edge） 顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为： （Vx，Vy）。边是无序的，可以看成是（Vx，Vy），也可以看成是（Vy，Vx）。 弧（Arc） 若顶点间的边是有方向性（有序）的，则称该偶
3、对为弧。记为：Vx，Vy。弧是有序的，Vx，Vy表示从Vx到Vy。 弧头（Head） 弧的终点（TerminaL Node）称为弧头（方向前方）。 弧尾（Tail） 弧的起始点（Initial Node）称为弧尾（方向后方）。 弧 Vx，Vy表示为，,弧尾 弧头,Vx,Vy,四、顶点、邻接点,顶点（Vertex）: 图中的数据元素（结点）称为顶点。 如图G1、G2中的1、2，1，2。 邻接点（Adjacent） 无向图中，若边（x，y） E， 则x、y互为邻接点。 有向图中，若弧x，y E， 则y是x的邻接点，反之，不是。(弧头是弧尾的邻接点),五. 顶点的度（Degree）,在图中，一个结点
4、的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度与出度之和称为该结点的度。对于无向图来说，其中每一个结点的入度等于该结点的出度。图中结点的最大度称为图的度。,六. 路径、长度,路径（Path） 在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：（V1V2V3）或（V1V3）；而G2中，1到4的路径为。 长度（Length） 路径的长度是该路径上边或弧的数目。例如，G1中V1到V3的长度为1或2；而G2中1到4的长度为2。,图的应用实例,路径问题 城市中有许多街道，每一个十字
5、路口都可以看作图中的一个顶点，邻接两个十字路口之间的每一段街道既可以看作一条，也可以看作两条有向边。如果街道是双向的，就用两条有向边。如果街道是单向的，就用一条有向边。(路线咨询),2.6.2、图的存储结构,根据图的定义可知，图的逻辑结构分为两部分：V（顶点）和E（边或弧）的集合。因此， 用一个一维数组存放图中所有顶点数据； 用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为关联矩阵。 关联矩阵也称为邻接矩阵。,1、关联矩阵表示法,关联矩阵,定义 在关联矩阵R中，每一个元素R(i,j)的定义为 1 di是dj的前件 R(i，j) = 0 di不是dj的前件,例如,G2的关联矩阵为：
6、,注意：一定对称，对角线全为0,注意：不一定对称，对角线不一定为0,G1的关联矩阵为：,2、求值矩阵,关联矩阵只表示了图的结构，即图中各结点的前后件关系。但在许多实际问题中，还需要对两个关联结点之间的值进行运算。这就是说，除了要存储图中各结点值以及各结点之间的关系外，还必须存储图中每两个结点之间的求值函数。 为了表示有值图中每两个结点之间的求值函数，可以另外用一个求值矩阵V来存储。,例,3、邻接表表示法,邻接表这种存储结构也称为“顺序-索引-链接”存储结构。,用一个顺序存储空间来存储图中各结点的信息。数据域data与指针域link。,数据域存放图中编号为k的结点值；指针域link用于 链接相应
7、结点的后件，,对于图中每一个结点，构造一个单链表。该单链表的头指针即为顺序空间中的对应存储结点的指针域。 单链表中各存储结点的结构如图所示，其中num域用于存放图中某个结点的编号；val域用于存放编号为num结点的前件到num结点之间的求值函数值f， 如果不是有值图，则val域可以不要；next域用于指向与num结点是同一个前件的另一个后件信息的结点。,邻接表存储结构描述,C+语言描述 template struct node int num； T1 val； node *next；/下一个邻接点 ； template struct gpnode T2 data ； node * link；/
8、第1个邻接点 ；/头结点数组,无向图G1的邻接表,注：边无权，节点只需两个域,有向图G2的邻接表,描述：在有向图中，第i个单链表中结点的个数是顶点Vi的出度； 特点：求出度方便，求入度，必须遍历整个邻接表。,建立邻接表的算法,操作步骤： step1 初始化邻接表的n个头结点， Step2 读入一条弧或边的偶对i，j或（i，j）。 step3 申请一个结点S的空间，将S插入到第i个单链表中； step4 读下一条弧或边的偶对，若存在此弧或边，则继续执行step2；否则，结束。,template void Link_GP:creat_link_GP(int n ,T2 d) node *p; in
9、t k,m; nn = n;/n为图中节点个数 gp=new gpnodenn; for (k=0; kdata=dk; (gp+k)-link = NULL ; coutmv; while (m =0) p= new node; p-num = m; p-val = v; p-next = (gp+k)-link; (gp+k)-link = p; cinmv; return;,4、邻接多重表,在图中，每一条边连接了两个结点。在有些应用中，需要同时找到表示一条边的两个结点，此时，邻接表的存储方式就显得不太方便了。 在邻接多重表中，每条边用一个存储结点表示，每个存储结点由五个域组成，其中，Ma
10、rk为标志域，,2.6.3、图的遍历,图的遍历（Traversing Graph） 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程称为图的遍历。 图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。 因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组MARK，每访问一个顶点，便将其状态MARKi置为“真”。 常用的图的遍历方法有两种： 深度优先遍历法(纵向优先搜索法 ) 广度优先遍历法(横向优先搜索法 ),一、 深度优先遍历法,算法思想： step1 从图中某个顶点V0出发，并访问此顶点； step2 从V0出发，访问与V0邻接
11、的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未访问过的邻接点为止。 step3 如果是连通图，从任一顶点V0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。,深度优先遍历法举例,遍历过程 访问顶点 边,起始顶点V1 V1 V1的第1个邻接点V3 V3 （V1，V3） V3的第1个邻接点V1已访问，取下 一个邻接点V5 V5 （V3，V5） V5的第1个邻接点V3已访问，取下 一个邻接点V2 V2 （V5，V2） V2的两个邻接点均被访问， 回
12、退到V5，V5的邻接点均被访问， 回退到V3，V3的邻接点均被访问 ， 回退到V1，V1的另一个邻接点V4 未被访问 V4 （V1，V4） V4的第一个邻接点V1已被访问， 另一个邻接点V6未被访问 V6 （V4，V6） V6的邻接点被访问，回退到V4 V4的邻接点均被访问 回退到V1，返回到出发点，遍历结束。,遍历产生的结果,深度优先遍历G6所走过的序列： V1 V3 V5 V2 V4 V6 所走过的边： （V1，V3），（V3，V5），（V5，V2），（V1，V4），（V4，V6）,template void Link_GP:Dfs_Link_GP( ) int *mark = new i
13、nt nn;/对已经访问的顶点做标记 int k; for(k = 0 ; k nn ; k+) markk=0; for( k = 0; k nn ; k +) if(markk=0) dfs(gp , k , mark); coutendl; delete mark; return; ,template static Link_GP:dfs(gpnode* q, int k , int * mark) node *p; coutdatalink; while ( p!= NULL ) if (mark(p-num)-1 = 0) dfs(q , p-num-1,mark); p=p-nex
14、t; return; ,课堂练习,2. 广度优先遍历算法,先访问第1个顶点所有邻接点后，再访问下一个顶点所有未被访问的邻接点。 算法思想： step1 从图中某个顶点V0出发，并访问此顶点； step2 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，,Wk;然后,依此从W1,W2,Wk出发访问各自未被访问的邻接点。 step3 重复step2，直到全部顶点都被访问为止。,2、广度（宽度）优先搜索:,图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：队列,1,2,12,11,3,6,7,10,4,5,8,9,1,2,12,11,3,6,7,1
15、0,4,5,8,9,遍历产生的结果,广度优先遍历G6所走过的序列： V1 V3 V2 V4 V5 V6 所走过的边： (V1，V3），（V1，V2），（V1，V4），（V3，V5），（V4，V6）,课堂练习,template void Link_GP: BFS_link_GP() int *mark ; node * p; sq_Queue q(nn) ; mark = new intnn; for(k=0 ; k data ; q.ins_sq_Queue(k);,while(q.flag_sq_Queue() ) k=q.del_sq_Queue(); p=(gp+k)-link; while (p!= NULL) k = p-num - 1; if(markk = 0) cout data next / end of if cout endl ;delete mark ; return ;,总结,图的定义 图的基本概念 图的遍历,