计算机软件基础(自考本科图)分析PPT课件

计算机软件的基础，第二编数据结构的基础，第十一章图，第一，简单概念，第一.图的定义，(1)图g :由一个非空的无限顶点集合v和一个无限边(或弧)集合e组成。 G=(V，e )，1，2，3，4，5，G=(V，e ) v= 1，2，3，4，5 e= 1，2 )，(1，4 )，(2，3 )，(2，5 )，(3，5 ) ，(2)无向图：顶点间的连接没有方向性的图。 注意：在无向图中，顶点之间的连接称为边。 一、简单概念、一、图的定义、注意：图中有顶点之间的连接，称为弧。 (3)有向图：顶点间的连接有方向性的图。，1，2，3，4，5，G=(V，e)v=，1，简单的概念，(1)完全无向图：从图中的哪个顶点到其他顶点，有直接存在于边上的无向图。 例如：1，2，3，4，5，注意：具有n个顶点的e条边的完全无向图：2 .基本用语，一个简单的概念，(2)完全无向图：从图中的任何一个顶点到其馀的顶点，有直接弧存在的有向图。 例如，、1、2、3、4，注意：具有n个顶点的e条边的完整有向图表示，、1、简单的概念，(3)两个顶点的相邻，(1)在无向图表中，在顶点Vi和Vj之间有边，顶点Vi和Vj相互邻接，2 )有向图表示如果从顶点Vi到顶点Vj有弧，则顶点Vi和Vj相邻，但Vj和Vi不相邻，另一方面，简单的概念，(4)顶点的度，(1)无向图的顶点的度是与该顶点相邻的边的数量，(2)有向图的顶点的度是该顶点的入度和出度之和，有向图的顶点的入度， 若是进入该顶点弧的数量，则有向图的顶点的出度，若是远离该顶点的弧的数量，则一般简单概念、(5)简单路径、(1)路径：在无向图中，将由从Vi点到Vj点的边构成的序列称为路径，在有向图中，将由从Vi点到Vj点的弧构成的有向序列称为路径2 )简单路径：无重复点的路径。 另一方面，简单的概念，(6)简单的电路，(1)电路：图中从某一点返回该点的路径，(2)简单的电路：仅起点和终点重复，其他点不重复的电路。 (1)图的邻接矩阵：描述图中的两个顶点间的邻接关系的矩阵。 (2)相邻矩阵的结构：或n*n次方阵，各行或各列对应于图中的顶点，通常，Aij的顶点值为Aij=， 1 :表示存在从顶点Vi到顶点Vj边(或弧)，0 :表示不存在从顶点Vi到顶点Vj的边(或弧)，2，图的存储结构，例1 :如下的无向图G1的邻接矩阵，0，1，0，1，0，1，0，1，0，1，1，1，0，1，1，1，1，1，0，1，1，1，1，1，0，1，0 1，1，1，1，1，1，0，1，0，0，0，0，0，0，2，图中的存储结构，例2 :到图G2的相邻矩阵写作：0，1，0，0，0，0，0，1，1，0，0，0，0，0，0，0，0，0，2，图中的存储结构，和(3)图中的相邻矩阵的性质： 1 )图邻接矩阵是唯一的，2 )邻接矩阵中，各行的非零个数是与该行对应的顶点的出度即各列的非零个数是与该列对应的顶点的入度，3 )无向图和完全有向图的邻接矩阵是对称的矩阵，二是图的存储结构，(4) 创建无向图邻接矩阵的算法： step1:输入顶点个数n和边数e，step2:清零邻接矩阵，分别输入step3边的2个顶点I和j，设Aij=1，Aji=1。 另外，图2的存储结构，(4)生成无向图邻接矩阵的算法记述：voidcreat(G，An 1，n，e)scanf(%d”，%d”，图2的存储结构，例如，(09.4 )二维阵列A33表示三节点无向图的邻接矩阵。 编制程序，从键盘输入邻接矩阵的数据，求出该无向图的边数和各节点的度数，并输出求出的结果。，1，2，3，2，图的存储结构，解：#includemain()inta33，I，j，b，s； /b :累计节点的角度s :累计无向图的角度s=0 for(i=0； i3； i )/输入邻接矩阵的数据for (j=0； j3； j )scanf(%d”，/输出图的边数)、二、图的存储结构、2 .用邻接链接表存储图，(1)图的邻接链接表：也称为邻接链接表，由n个链接表构成，各个链接表由标题节点和表节点构成。 1 )标题节点：与图中的节点相对应；2 )显示节点：标题节点表示的顶点的所有相邻点。 在该图的存储结构(例如，、标题节点、显示节点、二、该图的存储结构；(2)该图的相邻表的性质选择三、图的扫描、1 .图的扫描、2 .深度优先扫描、深度扫描。 口诀：小号优先； 刨根问底。 3、优先扫描广范围，扫描广范围，口诀：小号优先； 席卷四周。 另外，图中的扫描，例1:(2010.4 )下图所示的无方向图分别按邻接顶点编号从小到大的顺序给出宽度优先扫描与深度优先扫描的顶点序列。 此外，从解：宽度优先扫描、深度优先扫描、1237456、1245637、三次图表扫描，例2:(2008.4 )下图、解：宽度优先扫描：(1)顶点1起，按照邻接顶点编号从小到大的顺序赋予宽度优先扫描的顶点序列。 1256734、4、最小生成树无向图的应用，1 .相关概念，(1)连通图：从图中的任何点，都可以直接或间接到达其馀点的图。3、4、5、4、最小生成树的无向图的应用、1 .相关概念、(2)子图：如果图g-1的所有顶点和边完全包含在图g中，则将图g-1称为图g的子图。 (3)图的连通成分：研究的图的最大连通的子图。 注意：在连通图中，其连通成分是其本身。1、2、4、1、2、3、4、最小生成树的无向图的应用、2 .图的最小生成树、(1)图的生成树：指示该图的最小连通性的子图。 1 )“最小”的意思：一个图的生成树有n个顶点，n-1边，多边环绕生成树，至少一边不连通生成树，2 )连通图的必要条件：一个连通图，有n个顶点，至少有n-1边。 另外，最小生成树无向图的应用，例如，图a的部分生成树如b所示，结论：可以在一个图中生成多个树。 四、最小生成树无向图的应用、(2)最小生成树：各边权值之和最小的生成树。 (3)求最小生成树的方法巡航卷曲法，口诀：选择包含按权重升序选择边的所有顶点。 确保树的联系。 四、最小生成树无向图的应用例： (2008.4 )对于下图，(2)给出巡航卷曲法构造的最小生成树。四、最小生成树的无向图的应用，例11-4下图显示贫困地区的位置图，顶点显示贫困县，边的权值显示各县之间的距离，假定修道单位的成本相同，询问如何修道。1，6，4，15，10，8，4，16，1，15，10，4，8，16，5，拓扑排序有向图的应用，1 .关于名词，15，10，8，16，15，10，8，16，10，8，16，10，8，16，10，10，8，16，10，8，16 ，(2)拓扑序列：用AOV网构筑的线性序列。 (3)拓扑排序：构建拓扑序列的过程。 五、拓扑排序在图中有应用，2 .有构建拓扑序列的过程，step 13360输出输入度为零的节点，step 23360删除从该节点引出的所有箭头，step :最后的节点输出另一方面，拓扑排序可以应用于该图中，例如(09.4 )写入以下AOV网的所有拓扑排序序列，并从step 23360输出其输入密度为零的节点拓扑排名在图中有应用，表11-1是某工厂机床的检查工序例，e、a、f、g、b，、5、拓扑排