计算机软件技术基础课件-6(图).ppt

《计算机软件技术基础课件-6(图).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、图的定义和基本术语2、图的存储结构3、图的遍历图1、图的定义和基本术语定义215431324无向图有向图图：是由顶点集合和顶点间关系组成，记作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={，

2、,v3>，，}对右图：图中有序对称为弧，其中Vi为弧尾，Vj为弧头。此时≠。有向图记作G（V，A）。1、图的定义和基本术语路径：在图中，从顶点Vp到顶点Vq的通路，它由顶点序列（Vp，Vi1，Vi2,…,Vik,Vq）来表示，其中相邻顶点两两构成一条边或弧。在有向图中，则称有向路径。路径长度：路径上边或弧的数目称。网络的路径长度为路径上各边(弧)的权值之和简单路径：在顶点序列中除第一个和最后一个顶点外，序列中其余顶点各不相同的路径。连通图：在无向图中，若从点Vi到Vj存在路径，则称Vi和Vj是连通的。若顶点集合V中，每

3、对不同顶点Vi，Vj都连通，则称图为连通图。基本术语度：在无向图中，与某顶点相连的边的数目称为该顶点的度。入度、出度：在有向图中，以某顶点为尾的（初始点）的弧的数目称为该顶点的出度；而以该顶点为头（终端点）的弧的数目称为该顶点的入度。网：若无向图中每条边附一个对应的数（权），则称该图为网。有向网：弧上带权的有向图称为有向网。215431921113151324215156网有向网2、图的存储结构邻接矩阵—关系(联)矩阵是表示顶点之间相邻关系的矩阵。对一个有n个顶点的图，它的邻接矩阵是具有下列性质的n阶方阵：A[i,j]=1若(Vi,Vj)或是图中的边或弧0反之对于网，A[i

4、,j]=wij若(Vi,Vj)或是图中的边或弧，wij为边或弧的权值。0反之借助于邻接矩阵，能够判定任意两个顶点之间是否有边（弧）相连，亦能求得各个顶点的度。在无向图中，顶点的度是邻接矩阵中该点所在行（列）的元素之和；在有向图中，顶点的出度是该顶点所在行的元素之和，顶点的入度是顶点所在列的元素之和。1234512345123412342154313242、图的存储结构对于用邻接矩阵表示的图，在高级语言（VB）中可以这样定义：Enumadj01EndEnumTypeGraphdimvexs(1ton)asdatatype//存放顶点信息dimadjmatrix(1ton,1t

5、on)asadjEndtype定义一个含两个成员：0，1的枚举类型定义一个图邻接表顶点的邻接表：对一个有n个顶点的图，对图中每个顶点建立一个单链表，这样就将建立n个单链表，这n个单链表就称为一个图的邻接表。若以图中顶点Vi为头结点，把所有邻接于该点的顶点链接形成一个单链表，则这个单链表称为顶点Vi的邻接表。邻接表是图的一种链式存储结构。2、图的存储结构13241nil233nil42nil顶点表边表邻接表21543192111315邻接表1231311419nil531312nil4119nil5321nilnil14255211113nil边（弧）的结点的组成：邻接点域链域数据域邻接点

6、域，存放边(弧)的终点的序号；数据域，存放边(弧)的相关信息，如网中边上的权值；链域，指向邻接于顶点Vi的下一条边(弧)的结点；Typeedgeptr=^edgenodeedgenode=record//边表结点adjvex:1..n;//邻接点域next:edgeptr//链域end;vexnode=record//顶点表结点vextex:verttype;//顶点信息link:edgeptr//链域end;Adjlist=array[1..n]ofvexnode;//定义含有n个顶点的图2、图的存储结构注意：对于上述两种存储方式，邻接矩阵是唯一的而邻接表不唯一！高级语言中图的邻接表可

7、以如下定义（以pascal语言为例）：为了便于随即访问任一顶点的邻接表，将所有邻接表的头结点存储在一个数组中，图就用这个数组来表示。3、图的遍历深度优先搜索遍历算法逻辑：从图的某一个顶点V0出发遍历，首先访问该点，然后选择V0的一个尚未访问过的邻接点W，从W出发继续进行深度优先搜索，直到被访问的顶点其邻接点均被访问过为止。这时需要回溯到该顶点访问之前的顶点，继续访问其尚未访问过的邻接点，这样不断回溯直到起始点V0，使所有V0的邻接点