资源描述
1、图的定义和基本术语 2、图的存储结构 3、图的遍历,图,1、图的定义和基本术语,定义,无向图,有向图,图：是由顶点集合和顶点间关系组成，记作 G=（V，R）。,V为顶点集合，V= v1，v2，vn 。 R是两个顶点之间的关系的集合。,无向图：当图中顶点之间关系为无序时，称为无向图。,有向图：当图中顶点之间关系为有序时，称为有向图。,图中无序对(Vi,Vj)=(Vj,Vi)，称为边。无向图记作G（V，E）。,V=（v1，v2，v3，v4，v5）,E= (v1,v2)，(v1,v3)，(v1,v4)，(v2,v3)，(v3,v5) ,对左图：,V=（v1，v2，v3，v4）,E= ， ,对右图：,图中有序对称为弧，其中Vi为弧尾，Vj为弧头。此时 。有向图记作G（V，A）。,1、图的定义和基本术语,路径：在图中，从顶点Vp到顶点Vq的通路，它由顶点序列（Vp，Vi1，Vi2, ,Vik,Vq）来表示，其中相邻顶点两两构成一条边或弧。在有向图中，则称有向路径。,路径长度：路径上边或弧的数目称。网络的路径长度为路径上各边(弧)的权值之和,简单路径：在顶点序列中除第一个和最后一个顶点外，序列中其余顶点各不相同的路径。,连通图：在无向图中，若从点Vi到Vj存在路径，则称Vi和Vj是连通的。若顶点集合V中，每对不同顶点Vi，Vj都连通，则称图为连通图。,基本术语,度：在无向图中，与某顶点相连的边的数目称为该顶点的度。,入度、出度：在有向图中，以某顶点为尾的（初始点）的弧的数目称为该顶点的出度；而以该顶点为头（终端点）的弧的数目称为该顶点的入度。,网：若无向图中每条边附一个对应的数（权），则称该图为网。,有向网：弧上带权的有向图称为有向网。,网,有向网,2、图的存储结构,邻接矩阵关系(联)矩阵,是表示顶点之间相邻关系的矩阵。对一个有n个顶点的图，它的邻接矩阵是具有下列性质的n阶方阵：,Ai,j=,对于网，,Ai,j=,借助于邻接矩阵，能够判定任意两个顶点之间是否有边（弧）相连，亦能求得各个顶点的度。 在无向图中，顶点的度是邻接矩阵中该点所在行（列）的元素之和；在有向图中，顶点的出度是该顶点所在行的元素之和，顶点的入度是顶点所在列的元素之和。,2、图的存储结构,对于用邻接矩阵表示的图，在高级语言（VB）中可以这样定义：,Enum adj 0 1 End Enum Type Graph dim vexs(1 to n) as datatype /存放顶点信息 dim adjmatrix(1 to n,1 to n) as adj End type,定义一个含两个成员：0，1的枚举类型,定义一个图,邻接表,顶点的邻接表：,对一个有n个顶点的图，对图中每个顶点建立一个单链表，这样就将建立n个单链表，这n个单链表就称为一个图的邻接表。,若以图中顶点Vi为头结点，把所有邻接于该点的顶点链接形成一个单链表，则这个单链表称为顶点Vi的邻接表。,邻接表是图的一种链式存储结构。,2、图的存储结构,顶点表,边表,边（弧）的结点的组成：,邻接点域，存放边(弧)的终点的序号；,数据域，存放边(弧)的相关信息，如网中边上的权值；,链域，指向邻接于顶点Vi的下一条边(弧)的结点；,Type edgeptr=edgenode edgenode=record /边表结点 adjvex:1 n; /邻接点域 next:edgeptr /链域 end; vexnode=record /顶点表结点 vextex:verttype; /顶点信息 link:edgeptr /链域 end; Adjlist=array1n of vexnode; /定义含有n个顶点的图,2、图的存储结构,注意：对于上述两种存储方式，邻接矩阵是唯一的而邻接表不唯一！,高级语言中图的邻接表可以如下定义（以pascal语言为例）：,为了便于随即访问任一顶点的邻接表，将所有邻接表的头结点存储在一个数组中，图就用这个数组来表示。,3、图的遍历,深度优先搜索遍历,算法逻辑：从图的某一个顶点V0出发遍历，首先访问该点，然后选择V0的一个尚未访问过的邻接点W，从W出发继续进行深度优先搜索，直到被访问的顶点其邻接点均被访问过为止。这时需要回溯到该顶点访问之前的顶点，继续访问其尚未访问过的邻接点，这样不断回溯直到起始点V0，使所有V0的邻接点都被访问到为止。,DFS（A，i） 1. visiti /访问顶点Vi 2. visitedi true; /置顶点被访问标志 3. For j=1 to n 4. If (Ai,j=1) and (not visitedj) then 5. DFS(A，j) 6. end(j) 7. return,采用邻接矩阵为图的存储结构时深度优先搜索遍历算法：,遍历结果：,3,2,4,9,1,6,5,8,7,深度优先遍历的特点：尽可能先对纵深方向进行搜索。,3、图的遍历,广度优先搜索遍历,算法逻辑：首先访问顶点V0，接着依次访问V0的所有邻接点V1、V2、Vk，然后再依次访问与V1、V2、Vk邻接的所有未曾访问过的顶点，依次类推，直至所有被访问到的顶点的邻接点都被访问过为止。,对于图的邻接矩阵存储结构，广度优先遍历的结果为：,3 2 6 1 4 5 9 7 8,广度优先遍历的特点：尽可能先对横向进行搜索。,3、图的遍历,广度优先搜索遍历算法流程：,V3,V2,V6,V1,V4,V5,V9,V7,V8,遍历次序：,由广度优先搜索遍历的逻辑可见，先访问的顶点其邻接顶点也先被访问，因此在算法中需引进一个队列保存已访问过的顶点！,
展开阅读全文