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

1 物料管理物料管理File2/23/20231Algorithms and DataStructures:files1、图的定义和基本术语、图的定义和基本术语2、图的存储结构、图的存储结构3、图的遍历、图的遍历图图2 物料管理物料管理File2/23/20232Algorithms and DataStructures:files1、图的定义和基本术语、图的定义和基本术语 定义定义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=，对右图：对右图：图中有序对图中有序对称为弧，其中称为弧，其中Vi为弧尾，为弧尾，Vj为弧头。此时为弧头。此时 。有向图记作。有向图记作G（V，A）。）。3 物料管理物料管理File2/23/20233Algorithms and DataStructures:files1、图的定义和基本术语、图的定义和基本术语路径路径：在图中，从顶点：在图中，从顶点Vp到顶点到顶点Vq的通路，它由顶点序列（的通路，它由顶点序列（Vp，Vi1，Vi2,Vik,Vq）来表示，）来表示，其中相邻顶点两两构成一条边或弧。在有向图中，则称有向其中相邻顶点两两构成一条边或弧。在有向图中，则称有向路径。路径。路径长度路径长度：路径上边或弧的数目称：路径上边或弧的数目称。网络的路径长度为路径上各边。网络的路径长度为路径上各边(弧弧)的权值的权值之和之和简单路径简单路径：在顶点序列中除第一个和最后一个顶点外，序列中其余顶点各不相：在顶点序列中除第一个和最后一个顶点外，序列中其余顶点各不相同的路径同的路径。连通图连通图：在无向图中，若从点：在无向图中，若从点Vi到到Vj存在路径，则称存在路径，则称Vi和和Vj是连通的是连通的。若顶点。若顶点集合集合V中，每对不同顶点中，每对不同顶点Vi，Vj都连通，则称图为连通图。都连通，则称图为连通图。基本术语基本术语度度：在无向图中，与某顶点相连的边的数目称为该顶点的度：在无向图中，与某顶点相连的边的数目称为该顶点的度。入度、出度入度、出度：在有向图中，以某顶点为尾的（初始点）的弧的数目称为：在有向图中，以某顶点为尾的（初始点）的弧的数目称为该顶点的出度；而以该顶点为头（终端点）的弧的数目称为该顶点的入该顶点的出度；而以该顶点为头（终端点）的弧的数目称为该顶点的入度度。网网：若无向图中每条边附一个对应的数：若无向图中每条边附一个对应的数（权），则称该图为网（权），则称该图为网。有向网有向网：弧上带权的有向图称为有向网：弧上带权的有向图称为有向网。215431921113151324215156网网有向网有向网4 物料管理物料管理File2/23/20234Algorithms and DataStructures:files2、图的存储结构、图的存储结构 邻接矩阵邻接矩阵关系关系(联联)矩阵矩阵是表示顶点之间相邻关系的矩阵。对一个有是表示顶点之间相邻关系的矩阵。对一个有n个顶点的图，它的邻接矩阵是具个顶点的图，它的邻接矩阵是具有下列性质的有下列性质的n阶方阵：阶方阵：Ai,j=1 若若(Vi,Vj)或或是图中的边或弧是图中的边或弧0 反之反之对于网，对于网，Ai,j=wij若若(Vi,Vj)或或是图中的边或弧，是图中的边或弧，wij为边或弧为边或弧的权值。的权值。0反之反之借助于邻接矩阵，能够判定任意两个顶点之间是否有边（弧）相连，亦能求得各个顶借助于邻接矩阵，能够判定任意两个顶点之间是否有边（弧）相连，亦能求得各个顶点的度。点的度。在无向图中，顶点的度是邻接矩阵中该点所在行（列）的元素之和；在有向图中，顶在无向图中，顶点的度是邻接矩阵中该点所在行（列）的元素之和；在有向图中，顶点的出度是该顶点所在行的元素之和，顶点的入度是顶点所在列的元素之和。点的出度是该顶点所在行的元素之和，顶点的入度是顶点所在列的元素之和。1 2 3 4 5 123451 2 3 4 12342154313245 物料管理物料管理File2/23/20235Algorithms and DataStructures:files2、图的存储结构、图的存储结构对于用邻接矩阵表示的图，在高级语言（对于用邻接矩阵表示的图，在高级语言（VB）中可以这样定义：）中可以这样定义：Enum adj 0 1End EnumType Graph dim vexs(1 to n)as datatype /存放顶点信息存放顶点信息 dim adjmatrix(1 to n,1 to n)as adjEnd type定义一个含两个成员定义一个含两个成员：0，1的枚举类型的枚举类型定义一个图定义一个图 邻接表邻接表顶点的邻接表：顶点的邻接表：对一个有对一个有n个顶点的图，对图中每个顶点建立一个单链表，这样就将建立个顶点的图，对图中每个顶点建立一个单链表，这样就将建立n个单链表，这个单链表，这n个单链表就称为一个图的邻接表。个单链表就称为一个图的邻接表。若以图中顶点若以图中顶点Vi为头结点，把所有邻接于该点的顶点链接为头结点，把所有邻接于该点的顶点链接形成一个单链表，则这个单链表称为顶点形成一个单链表，则这个单链表称为顶点Vi的邻接表。的邻接表。邻接表是图的一种链式存储结构。邻接表是图的一种链式存储结构。6 物料管理物料管理File2/23/20236Algorithms and DataStructures:files2、图的存储结构、图的存储结构13241nil233nil42nil顶点表顶点表边表边表邻接表邻接表21543192111315邻接表邻接表12 313114 19nil531 312nil41 19nil53 21nilnil14255 211113nil7 物料管理物料管理File2/23/20237Algorithms and DataStructures:files边（弧）的结点的组成：边（弧）的结点的组成：邻接点域邻接点域链域链域数据域数据域邻接点域，存放边邻接点域，存放边(弧弧)的终点的序号；的终点的序号；数据域，存放边数据域，存放边(弧弧)的相关信息，如网中边上的权值；的相关信息，如网中边上的权值；链域，指向邻接于顶点链域，指向邻接于顶点Vi的下一条边的下一条边(弧弧)的结点；的结点；Type edgeptr=edgenode edgenode=record /边表结点边表结点 adjvex:1.n;/邻接点域邻接点域 next:edgeptr /链域链域 end;vexnode=record /顶点表结点顶点表结点 vextex:verttype;/顶点信息顶点信息 link:edgeptr /链域链域 end;Adjlist=array1.n of vexnode;/定义含有定义含有n个顶点的图个顶点的图2、图的存储结构、图的存储结构注意：对于上述两种存储方式，邻接矩阵是唯一的而邻接表不唯一！注意：对于上述两种存储方式，邻接矩阵是唯一的而邻接表不唯一！高级语言中图的邻接表可以如下定义（以高级语言中图的邻接表可以如下定义（以pascal语言为例）：语言为例）：为了便于随即访为了便于随即访问任一顶点的邻问任一顶点的邻接表，将所有邻接表，将所有邻接表的头结点存接表的头结点存储在一个数组中，储在一个数组中，图就用这个数组图就用这个数组来表示。来表示。8 物料管理物料管理File2/23/20238Algorithms and DataStructures:files3、图的遍历、图的遍历 深度优先搜索遍历深度优先搜索遍历算法逻辑：从图的某一个顶点算法逻辑：从图的某一个顶点V0出发遍历，首先访问该点，然后选择出发遍历，首先访问该点，然后选择V0的一的一个尚未访问过的邻接点个尚未访问过的邻接点W，从，从W出发继续进行深度优先搜索，直到被访问的出发继续进行深度优先搜索，直到被访问的顶点其邻接点均被访问过为止。这时需要回溯到该顶点访问之前的顶点，继顶点其邻接点均被访问过为止。这时需要回溯到该顶点访问之前的顶点，继续访问其尚未访问过的邻接点，这样不断回溯直到起始点续访问其尚未访问过的邻接点，这样不断回溯直到起始点V0，使所有，使所有V0的邻的邻接点都被访问到为止。接点都被访问到为止。326451987DFS（A，i）1.visiti /访问顶点访问顶点Vi2.visitedi true;/置顶点被访问标志置顶点被访问标志3.For j=1 to n 4.If (Ai,j=1)and (not visitedj)then5.DFS(A，j)6.end(j)7.return采用邻接矩阵为图的存储结构时深度优先搜采用邻接矩阵为图的存储结构时深度优先搜索遍历算法：索遍历算法：遍历结果：遍历结果：3 2 4 9 1 6 5 8 7深度优先遍历的特点：尽可能先对纵深方向进行搜索。深度优先遍历的特点：尽可能先对纵深方向进行搜索。9 物料管理物料管理File2/23/20239Algorithms and DataStructures:files3、图的遍历、图的遍历 广度优先搜索遍历广度优先搜索遍历算法逻辑：首先访问顶点算法逻辑：首先访问顶点V0，接着依次访问，接着依次访问V0的所有的所有邻接点邻接点V1、V2、Vk，然后再依次访问与然后再依次访问与V1、V2、Vk邻接的所有未曾访问过的顶点，依次类推，邻接的所有未曾访问过的顶点，依次类推，直至所有被访问到的顶点的邻接点都被访问过为止。直至所有被访问到的顶点的邻接点都被访问过为止。326451987第一层次第一层次第二层次第二层次第三层次第三层次对于图的邻接矩阵存储结构，对于图的邻接矩阵存储结构，广度优先遍历的结果为：广度优先遍历的结果为：3 2 6 1 4 5 9 7 8 1 2 3 4 5 6 7 8 9123456789起始访问点起始访问点广度优先遍历的特点：尽可能先对横向进行搜索。广度优先遍历的特点：尽可能先对横向进行搜索。10 物料管理物料管理File2/23/202310Algorithms and DataStructures:files访问访问Vi，置标志，置标志初始化队列初始化队列Vi入队入队队空？队空？队头元素队头元素V出队出队求求V的邻接点的邻接点WW存在？存在？W访问过？访问过？访问访问W，置标志并入队，置标志并入队求求V的下一个邻接点的下一个邻接点结束结束YNYNNY3、图的遍历、图的遍历广度优先搜索遍历算法流程：广度优先搜索遍历算法流程：0 1 2 3 4 5 6 7 8 9rearV3326451987V2 V6 V1 V4 V5 V9 V7 V8front遍历次序：遍历次序：由广度优先搜索遍历的逻辑可见，先访问的顶点其由广度优先搜索遍历的逻辑可见，先访问的顶点其邻接顶点也先被访问，因此在算法中需引进一个队邻接顶点也先被访问，因此在算法中需引进一个队列保存已访问过的顶点！列保存已访问过的顶点！