《计算机软件基础(自考本科图).ppt》由会员分享，可在线阅读，更多相关《计算机软件基础(自考本科图).ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机计算机 软件基础软件基础第二篇数据结构基础第二篇数据结构基础第十一章图第十一章图第十一章图第十一章图一、简单概念一、简单概念1.图的定义图的定义（1）图）图G：是由一个非空有穷的顶点集合：是由一个非空有穷的顶点集合V和一个有和一个有穷的边（或弧）集合穷的边（或弧）集合E组成。记作：组成。记作：G=（V，E）1 12 23 34 45 5G=（V，E）V=1,2,3,4,5E=(1,2),(1,4),(2,3),(2,5),(3,5)（2）无向图：顶点之间的连线不具有方向性的图。）无向图：顶点之间的连线不具有方向性的图。注意：注意：无向图中，顶点之间的连线，称为边。无向图中，顶点之间的连线
2、，称为边。一、简单概念一、简单概念1.图的定义图的定义注意：注意：有向图中，顶点之间的连线，称为弧。有向图中，顶点之间的连线，称为弧。（3）有向图：顶点之间的连线具有方向性的图。）有向图：顶点之间的连线具有方向性的图。1 12 23 34 45 5G=（V，E）V=1,2,3,4,5E=,一、简单概念一、简单概念（1）完全无向图：从图中任一顶点到其余顶点，都）完全无向图：从图中任一顶点到其余顶点，都有有直接直接边存在的无向图。如：边存在的无向图。如：1 12 23 34 45 5注意：注意：对于具有对于具有n个顶点，个顶点，e条边的完全无向图：条边的完全无向图：2.基本术语基本术语一、简单概念
3、一、简单概念（2）完全有向图：从图中任一顶点到其余顶点，都）完全有向图：从图中任一顶点到其余顶点，都有有直接直接弧存在的有向图。如：弧存在的有向图。如：1 12 23 34 4注意：注意：对于具有对于具有n个顶点，个顶点，e条边的完全有向图：条边的完全有向图：一、简单概念一、简单概念（3）两顶点的邻接）两顶点的邻接 1）对于无向图来说，如果顶点）对于无向图来说，如果顶点Vi与与Vj之间有边，之间有边，则称顶点则称顶点Vi与与Vj互为邻接；互为邻接；2）对于有向图来说，如果顶点）对于有向图来说，如果顶点Vi到顶点到顶点Vj有弧，有弧，则称顶点则称顶点Vi和和Vj是邻接，但是邻接，但Vj 和和和和
4、Vi 是不邻接的是不邻接的是不邻接的是不邻接的；一、简单概念一、简单概念（4）顶点的度）顶点的度1）无向图顶点的度，是与该顶点邻接的边的数目；）无向图顶点的度，是与该顶点邻接的边的数目；2）有向图顶点的度，是该顶点入度和出度之和；）有向图顶点的度，是该顶点入度和出度之和；有向图顶点的入度，是进入该顶点弧的数目；有向图顶点的入度，是进入该顶点弧的数目；有向图顶点的出度，是远离该顶点弧的数目；有向图顶点的出度，是远离该顶点弧的数目；一、简单概念一、简单概念（5）简单路径）简单路径1）路径：）路径：对于无向图来说，从对于无向图来说，从Vi点到点到Vj点的点的边边组成的组成的序列序列，称为路径；称为路
5、径；对于有向图来说，从对于有向图来说，从Vi点到点到Vj点的点的弧弧组成的组成的有向有向序列序列，称为路径。，称为路径。2）简单路径：没有重复点的路径。）简单路径：没有重复点的路径。一、简单概念一、简单概念（6）简单回路）简单回路1）回路：）回路：在图中，从某一点出发又回到该点的路径；在图中，从某一点出发又回到该点的路径；2）简单回路：）简单回路：只有起点和终点重复，其他点不重复的回路。只有起点和终点重复，其他点不重复的回路。二、图的存储结构二、图的存储结构1.用邻接矩阵存储图用邻接矩阵存储图（1）图的邻接矩阵：描述图中两个顶点之间邻接关）图的邻接矩阵：描述图中两个顶点之间邻接关系的矩阵。系的
6、矩阵。（2）邻接矩阵的结构：）邻接矩阵的结构：是一个是一个n*n阶的方阵，其中的每一行或每一列对应于阶的方阵，其中的每一行或每一列对应于图中的一个顶点；图中的一个顶点；一般情况下，一般情况下，Aij顶点的值如下：顶点的值如下：Aij=1：表示从顶点：表示从顶点Vi到顶点到顶点Vj有边（或弧）有边（或弧）0：表示从顶点：表示从顶点Vi到顶点到顶点Vj没有边（或弧）没有边（或弧）二、图的存储结构二、图的存储结构例例1：写出下列无向图：写出下列无向图G1的邻接矩阵的邻接矩阵1 12 24 43 35 5 0101010101010111010001100二、图的存储结构二、图的存储结构例例2：写出下
7、列有向图：写出下列有向图G2的邻接矩阵的邻接矩阵 01000001010001110000000001 12 24 43 35 5二、图的存储结构二、图的存储结构（3）图的邻接矩阵的性质：）图的邻接矩阵的性质：1）一个图的邻接矩阵是）一个图的邻接矩阵是唯一唯一的；的；2）邻接矩阵中，各行非零的个数为该行所对应顶点）邻接矩阵中，各行非零的个数为该行所对应顶点的的出度出度；各列非零的个数为该列所对应顶点的；各列非零的个数为该列所对应顶点的入度入度；3）无向图和完全有向图的邻接矩阵是一个）无向图和完全有向图的邻接矩阵是一个对称对称的矩的矩阵阵二、图的存储结构二、图的存储结构（4）建立）建立无向图无向
8、图邻接矩阵的算法：邻接矩阵的算法：step1：输入顶点的个数：输入顶点的个数n和边数和边数e；step2：将邻接矩阵清零；：将邻接矩阵清零；step3：分别输入：分别输入e条边的两个顶点条边的两个顶点i和和j，并且令，并且令Aij=1，Aji=1。二、图的存储结构二、图的存储结构（4）建立）建立无向图无向图邻接矩阵的算法描述：邻接矩阵的算法描述：void creat(G,A n+1,n,e)void creat(G,A n+1,n,e)scanf(%d ,%d ,&n,&e);/scanf(%d ,%d ,&n,&e);/输入图的输入图的输入图的输入图的顶点数顶点数顶点数顶点数和和和和边数边数
9、边数边数 for(i=1;i=n;i+)/for(i=1;i=n;i+)/将矩阵清零将矩阵清零将矩阵清零将矩阵清零 for(j=1;j=n;j+)for(j=1;j=n;j+)Aij=0;Aij=0;for(k=1;k=e;k+)/for(k=1;k=e;k+)/分别输入分别输入分别输入分别输入e e条边的两个顶点条边的两个顶点条边的两个顶点条边的两个顶点 scanf(%d,%d ,&i,&j)scanf(%d,%d ,&i,&j)Aij=1;Aij=1;Aji=1;Aji=1;二、图的存储结构二、图的存储结构例例：（：（09.4）设二维数组）设二维数组A33表示表示3节点无向图的邻节点无向图
10、的邻接矩阵。编写程序，接矩阵。编写程序，从键盘上输入邻接矩阵的数据从键盘上输入邻接矩阵的数据，求出该无向图的边数求出该无向图的边数以及以及各个节点的度数各个节点的度数，并，并输出所输出所求结果。求结果。1 12 23 3二、图的存储结构二、图的存储结构解：解：#include#includemain()main()int a33,i,j,b,s;/b int a33,i,j,b,s;/b：累积节点的度；：累积节点的度；：累积节点的度；：累积节点的度；s s：累积无向图的度：累积无向图的度：累积无向图的度：累积无向图的度 s=0;s=0;for(i=0;i3;i+)/for(i=0;i3;i+)
11、/输入邻接矩阵的数据输入邻接矩阵的数据输入邻接矩阵的数据输入邻接矩阵的数据 for(j=0;j3;j+)for(j=0;j3;j+)scanf(%d,&aij);scanf(%d,&aij);for(i=0;i3;i+)/for(i=0;i3;i+)/求各节点的度以及图的度求各节点的度以及图的度求各节点的度以及图的度求各节点的度以及图的度 b=0;b=0;for(j=0;j3;j+)for(j=0;j3;j+)if(aij=1)b=b+1;if(aij=1)b=b+1;printf(The degree of node%d:%dn,i,b);printf(The degree of node%
12、d:%dn,i,b);s=s+b;s=s+b;printf(The sum of edge is:%dn,s/2);/printf(The sum of edge is:%dn,s/2);/输出图的边数输出图的边数输出图的边数输出图的边数 二、图的存储结构二、图的存储结构2.用邻接链表存储图用邻接链表存储图（1）图的邻接链表：又称为邻接表，由）图的邻接链表：又称为邻接表，由n个单链表组个单链表组成，每一个单链表又由表头节点和表节点两部分构成。成，每一个单链表又由表头节点和表节点两部分构成。1)表头节点：对应于图中的一个节点；表头节点：对应于图中的一个节点；2)表节点：表头节点所代表顶点的所有邻
13、接点。表节点：表头节点所代表顶点的所有邻接点。二、图的存储结构二、图的存储结构例如：例如：1 12 24 43 35 5V1V1V3V3V4V4V2V2V5V5V2V2V2V2V1V1V1V1V2V2V4V4V3V3V4V4V3V3V3V3V5V5V5V5表头节点表头节点表节点表节点二、图的存储结构二、图的存储结构（2）图的邻接表的性质）图的邻接表的性质1)一个图的邻接表不是唯一的；一个图的邻接表不是唯一的；2)在无向图的邻接表中，各单链表表节点的个数为对在无向图的邻接表中，各单链表表节点的个数为对应表头节点（顶点）的度；应表头节点（顶点）的度；在有向图的邻接表中，各单链表表节点的个数为对应在
14、有向图的邻接表中，各单链表表节点的个数为对应表头节点（顶点）的出度。表头节点（顶点）的出度。三、图的遍历三、图的遍历1.图的遍历图的遍历2.深度优先遍历深度优先遍历深度遍历；深度遍历；访问图中各节点的过程。访问图中各节点的过程。口诀：口诀：小号优先；小号优先；刨根问底。刨根问底。3.广度优先遍历广度优先遍历广度遍历；广度遍历；口诀：口诀：小号优先；小号优先；横扫四周。横扫四周。三、图的遍历三、图的遍历例例1：（：（2010.4）如下图所示的无向图，分别按邻接顶）如下图所示的无向图，分别按邻接顶点序号由小到大顺序给出点序号由小到大顺序给出广度优先遍历广度优先遍历和和深度优先遍深度优先遍历历的顶点
15、序列。的顶点序列。解：解：广度优先遍历广度优先遍历深度优先遍历深度优先遍历12374561 13 37 72 24 45 56 61245637三、图的遍历三、图的遍历例例2：（：（2008.4）对于下图）对于下图解：解：广度优先遍历广度优先遍历:（1）从顶点）从顶点1出发，按邻接顶点序号由小到大的顺序出发，按邻接顶点序号由小到大的顺序给出广度优先遍历的顶点序列。给出广度优先遍历的顶点序列。1 13 37 72 24 45 56 61256734四、最小生成树四、最小生成树无向图的应用无向图的应用1.相关概念相关概念（1）连通图：从图中任意一点出发，都能直接或）连通图：从图中任意一点出发，都能
16、直接或间接到达其余点的图。间接到达其余点的图。1 12 23 34 45 56 67 7四、最小生成树四、最小生成树无向图的应用无向图的应用1.相关概念相关概念（2）子图：如果图）子图：如果图G1的所有顶点和边完全被图的所有顶点和边完全被图G包含，则称图包含，则称图G1为图为图G的子图。的子图。（3）图的连通分量：是指所研究图的）图的连通分量：是指所研究图的最大的连通的最大的连通的子图。子图。注意：注意：对于对于连通图连通图来说，其连通分量就是它本身。来说，其连通分量就是它本身。1 15 52 23 34 41 12 24 41 12 23 34 41 15 52 23 34 4四、最小生成树
17、四、最小生成树无向图的应用无向图的应用2.图的最小生成树图的最小生成树（1）图的生成树：指该图）图的生成树：指该图最小最小的的连通连通的子图。的子图。1）“最小最小”的含义：的含义：一个图的生成树有一个图的生成树有n个顶点，个顶点，n-1条边，如果多一条边，如果多一条边将使生成树产生条边将使生成树产生回路回路，少一条边将使生成树，少一条边将使生成树不连不连通通2）连通图的必要条件：）连通图的必要条件：一个连通图，具有一个连通图，具有n个顶点，则至少有个顶点，则至少有n-1条边。条边。四、最小生成树四、最小生成树无向图的应用无向图的应用例如：图例如：图a的的部分部分生成树如生成树如b所示所示1
18、12 24 43 35 51 12 24 43 35 51 12 24 43 35 51 12 24 43 35 5结论：结论：一个图一个图，可以，可以 生成生成多棵树。多棵树。四、最小生成树四、最小生成树无向图的应用无向图的应用（2）最小生成树：）最小生成树：各边权值之和为各边权值之和为最小最小的生成树。的生成树。（3）求最小生成树的方法）求最小生成树的方法克鲁斯卡尔法克鲁斯卡尔法口诀：口诀：权值升序选边；权值升序选边；包含所有顶点；包含所有顶点；禁止产生回路。禁止产生回路。确保树木连通。确保树木连通。四、最小生成树四、最小生成树无向图的应用无向图的应用例：例：（2008.4）对于下图）对于
19、下图（2）给出克鲁斯卡尔法构造的最小生成树。）给出克鲁斯卡尔法构造的最小生成树。1 13 37 72 24 45 56 66 67 718184 423232525121215158 85 5101020207 76 618181 16 64 45 512124 48 83 32 25 5四、最小生成树四、最小生成树无向图的应用无向图的应用例例11-4下图表示一个贫困地区的位置示意图，顶点表示贫困县，下图表示一个贫困地区的位置示意图，顶点表示贫困县，边上的权值表示各个县之间的里程，假设修路的单位造价相同，边上的权值表示各个县之间的里程，假设修路的单位造价相同，问如何修路造价最低。问如何修路造价
20、最低。18181 16 64 43 35 52 2151519192828101014148 84 48 816161 16 64 43 35 52 2151510108 84 416161 16 64 43 35 52 2151510104 48 81616五、拓扑排序五、拓扑排序有向图的应用有向图的应用1.有关名词有关名词（1）AOV网络图：又称为顶点活动网，是指用顶点网络图：又称为顶点活动网，是指用顶点表征各项活动、边表征活动发生先后顺序的有向图。表征各项活动、边表征活动发生先后顺序的有向图。（2）拓扑序列：由拓扑序列：由AOV网构造的网构造的线性序列线性序列。（3）拓扑排序：构造拓扑序
21、列的过程。拓扑排序：构造拓扑序列的过程。五、拓扑排序五、拓扑排序有向图的应用有向图的应用2.构造拓扑序列的步骤构造拓扑序列的步骤step1:输出输出入度入度为零的节点；为零的节点；step2:划去从该节点引出的所有箭线；划去从该节点引出的所有箭线；step3:重复重复step1step2，直到输出完最后一个节点。，直到输出完最后一个节点。五、拓扑排序五、拓扑排序有向图的应用有向图的应用例：（例：（09.4）写出下列）写出下列AOV网的所有拓扑排序序列网的所有拓扑排序序列7 71 16 65 54 43 32 2step1:输出输出入度入度为零的为零的节点；节点；step2:划去从该节点引出的划
22、去从该节点引出的所有箭线；所有箭线；五、拓扑排序五、拓扑排序有向图的应用有向图的应用表表11-1是某工厂机床检修工序示例是某工厂机床检修工序示例顺序号工序代号工序名称紧前工序1A拆卸无2B机件检查A3C电器检查A4D零件修复B5E零件加工B6F组装C、D、E7G试车FE EA AF FGGD DC CB B五、拓扑排序五、拓扑排序有向图的应用有向图的应用例例11-5 有六项任务，每项任务要求的前驱活动如下：有六项任务，每项任务要求的前驱活动如下：C1：C2，C5，C6C2：C3，C6C3：C4C4：无：无C5：C4，C6C6：C3，C4C C6 6C C4 4C C1 1C C2 2C C5 5C C3 3五、拓扑排序五、拓扑排序有向图的应用有向图的应用3.拓扑排序小结拓扑排序小结（1）拓扑排序只能针对有向无环图进行；）拓扑排序只能针对有向无环图进行；（2）一个确定的）一个确定的AOV网，其拓扑序列不是唯一的。网，其拓扑序列不是唯一的。