计算机软件基础(自考本科图)

1、1. 图的定义图的定义（1）图）图G：是由一个非空有穷的顶点集合：是由一个非空有穷的顶点集合V和一个有和一个有穷的边（或弧）集合穷的边（或弧）集合E组成。记作：组成。记作： G=（V，E）G=（V，E）V=1,2,3,4,5E=(1,2),(1,4),(2,3),(2,5),(3,5)（2）无向图：顶点之间的连线不具有方向性的图。）无向图：顶点之间的连线不具有方向性的图。注意：注意：无向图中，顶点之间的连线，称为边。无向图中，顶点之间的连线，称为边。1. 图的定义图的定义注意：注意：有向图中，顶点之间的连线，称为弧。有向图中，顶点之间的连线，称为弧。（3）有向图：顶点之间的连线具有方向性的图。

2、）有向图：顶点之间的连线具有方向性的图。G=（V，E）V=1,2,3,4,5E=,（1）完全无向图：从图中任一顶点到其余顶点，都）完全无向图：从图中任一顶点到其余顶点，都有有直接直接边存在的无向图。如：边存在的无向图。如：注意：注意：对于具有对于具有n个顶点，个顶点，e条边的完全无向图：条边的完全无向图： 2. 基本术语基本术语)n(ne121（2）完全有向图：从图中任一顶点到其余顶点，都）完全有向图：从图中任一顶点到其余顶点，都有有直接直接弧存在的有向图。如：弧存在的有向图。如：注意：注意：对于具有对于具有n个顶点，个顶点，e条边的完全有向图：条边的完全有向图： )n(ne1（3）两顶点的邻

3、接）两顶点的邻接 1）对于无向图来说，如果顶点）对于无向图来说，如果顶点Vi与与Vj之间有边，之间有边，则称顶点则称顶点Vi与与Vj互为邻接；互为邻接； 2）对于有向图来说，如果顶点）对于有向图来说，如果顶点Vi到顶点到顶点Vj有弧，有弧，则称顶点则称顶点Vi和和Vj是邻接，但是邻接，但VjVi；（4）顶点的度）顶点的度1）无向图顶点的度，是与该顶点邻接的边的数目；）无向图顶点的度，是与该顶点邻接的边的数目；2）有向图顶点的度，是该顶点入度和出度之和；）有向图顶点的度，是该顶点入度和出度之和；有向图顶点的入度，是进入该顶点弧的数目；有向图顶点的入度，是进入该顶点弧的数目；有向图顶点的出度，是远

4、离该顶点弧的数目；有向图顶点的出度，是远离该顶点弧的数目；（5）简单路径）简单路径1）路径：）路径： 对于无向图来说，从对于无向图来说，从Vi点到点到Vj点的点的边边组成的组成的序列序列，称为路径；称为路径； 对于有向图来说，从对于有向图来说，从Vi点到点到Vj点的点的弧弧组成的组成的有向有向序列序列，称为路径。，称为路径。2）简单路径：没有重复点的路径。）简单路径：没有重复点的路径。（6）简单回路）简单回路1）回路：）回路： 在图中，从某一点出发又回到该点的路径；在图中，从某一点出发又回到该点的路径；2）简单回路：）简单回路： 只有起点和终点重复，其他点不重复的回路。只有起点和终点重复，其他

5、点不重复的回路。1. 用邻接矩阵存储图用邻接矩阵存储图（1）图的邻接矩阵：描述图中两个顶点之间邻接关）图的邻接矩阵：描述图中两个顶点之间邻接关系的矩阵。系的矩阵。（2）邻接矩阵的结构：）邻接矩阵的结构：是一个是一个n*n阶的方阵，其中的每一行或每一列对应于阶的方阵，其中的每一行或每一列对应于图中的一个顶点；图中的一个顶点；一般情况下，一般情况下，Aij顶点的值如下：顶点的值如下：Aij=1：表示从顶点：表示从顶点Vi到顶点到顶点Vj有边（或弧）有边（或弧）0：表示从顶点：表示从顶点Vi到顶点到顶点Vj没有边（或弧）没有边（或弧）例例1：写出下列无向图：写出下列无向图G1的邻接矩阵的邻接矩阵 0

6、101010101010111010001100例例2：写出下列有向图：写出下列有向图G2的邻接矩阵的邻接矩阵 0100000101000111000000000（3）图的邻接矩阵的性质：）图的邻接矩阵的性质：1）一个图的邻接矩阵是）一个图的邻接矩阵是唯一唯一的；的；2）邻接矩阵中，各行非零的个数为该行所对应顶点）邻接矩阵中，各行非零的个数为该行所对应顶点的的出度出度；各列非零的个数为该列所对应顶点的；各列非零的个数为该列所对应顶点的入度入度；3）无向图和完全有向图的邻接矩阵是一个）无向图和完全有向图的邻接矩阵是一个对称对称的矩的矩阵阵（4）建立）建立无向图无向图邻接矩阵的算法：邻接矩阵的算法

7、：step1：输入顶点的个数：输入顶点的个数n和边数和边数e；step2：将邻接矩阵清零；：将邻接矩阵清零；step3：分别输入：分别输入e条边的两个顶点条边的两个顶点i和和j，并且令，并且令Aij=1， Aji=1。（4）建立）建立无向图无向图邻接矩阵的算法描述：邻接矩阵的算法描述：例例：（：（09.4）设二维数组）设二维数组A33表示表示3节点无向图的邻节点无向图的邻接矩阵。编写程序，接矩阵。编写程序，从键盘上输入邻接矩阵的数据从键盘上输入邻接矩阵的数据，求出该无向图的边数求出该无向图的边数以及以及各个节点的度数各个节点的度数，并，并输出所输出所求结果。求结果。011101110解：解：2

8、. 用邻接链表存储图用邻接链表存储图（1）图的邻接链表：又称为邻接表，由）图的邻接链表：又称为邻接表，由n个单链表组个单链表组成，每一个单链表又由表头节点和表节点两部分构成。成，每一个单链表又由表头节点和表节点两部分构成。1)表头节点：对应于图中的一个节点；表头节点：对应于图中的一个节点；2)表节点：表头节点所代表顶点的所有邻接点。表节点：表头节点所代表顶点的所有邻接点。例如：例如：表头节点表头节点表节点表节点（2）图的邻接表的性质）图的邻接表的性质1)一个图的邻接表不是唯一的；一个图的邻接表不是唯一的；2)在无向图的邻接表中，各单链表表节点的个数为对在无向图的邻接表中，各单链表表节点的个数为

9、对应表头节点（顶点）的度；应表头节点（顶点）的度；在有向图的邻接表中，各单链表表节点的个数为对应在有向图的邻接表中，各单链表表节点的个数为对应表头节点（顶点）的出度。表头节点（顶点）的出度。1. 图的遍历图的遍历2. 深度优先遍历深度优先遍历深度遍历；深度遍历； 访问图中各节点的过程。访问图中各节点的过程。口诀：口诀：小号优先；小号优先；刨根问底。刨根问底。3. 广度优先遍历广度优先遍历广度遍历；广度遍历；口诀：口诀：小号优先；小号优先；横扫四周。横扫四周。例例1：（：（2010.4）如下图所示的无向图，分别按邻接顶）如下图所示的无向图，分别按邻接顶点序号由小到大顺序给出点序号由小到大顺序给出

10、广度优先遍历广度优先遍历和和深度优先遍深度优先遍历历的顶点序列。的顶点序列。解：解：广度优先遍历广度优先遍历深度优先遍历深度优先遍历12374561245637例例2：（：（2008.4）对于下图）对于下图解：解：广度优先遍历广度优先遍历:（1）从顶点）从顶点1出发，按邻接顶点序号由小到大的顺序出发，按邻接顶点序号由小到大的顺序给出广度优先遍历的顶点序列。给出广度优先遍历的顶点序列。12567341. 相关概念相关概念（1）连通图：从图中任意一点出发，都能直接或）连通图：从图中任意一点出发，都能直接或间接到达其余点的图。间接到达其余点的图。1. 相关概念相关概念（2）子图：如果图）子图：如果图

11、G1的所有顶点和边完全被图的所有顶点和边完全被图G包含，则称图包含，则称图G1为图为图G的子图。的子图。（3）图的连通分量：是指所研究图的）图的连通分量：是指所研究图的最大的连通的最大的连通的子图。子图。注意：注意：对于对于连通图连通图来说，其连通分量就是它本身。来说，其连通分量就是它本身。2. 图的最小生成树图的最小生成树（1）图的生成树：指该图）图的生成树：指该图最小最小的的连通连通的子图。的子图。1）“最小最小”的含义：的含义： 一个图的生成树有一个图的生成树有n个顶点，个顶点，n-1条边，如果多一条边，如果多一条边将使生成树产生条边将使生成树产生回路回路，少一条边将使生成树，少一条边将

12、使生成树不连不连通通2）连通图的必要条件：）连通图的必要条件： 一个连通图，具有一个连通图，具有n个顶点，则至少有个顶点，则至少有n-1条边。条边。例如：图例如：图a的的部分部分生成树如生成树如b所示所示结论：结论：一个图一个图，可以，可以 生成生成多棵树。多棵树。（2）最小生成树：）最小生成树： 各边权值之和为各边权值之和为最小最小的生成树。的生成树。（3）求最小生成树的方法）求最小生成树的方法克鲁斯卡尔法克鲁斯卡尔法口诀：口诀：权值升序选边；权值升序选边；包含所有顶点；包含所有顶点；禁止产生回路。禁止产生回路。确保树木连通。确保树木连通。例：例： （2008.4）对于下图）对于下图（2）给

13、出克鲁斯卡尔法构造的最小生成树。）给出克鲁斯卡尔法构造的最小生成树。例例11-4下图表示一个贫困地区的位置示意图，顶点表示贫困县，下图表示一个贫困地区的位置示意图，顶点表示贫困县，边上的权值表示各个县之间的里程，假设修路的单位造价相同，边上的权值表示各个县之间的里程，假设修路的单位造价相同，问如何修路造价最低。问如何修路造价最低。1. 有关名词有关名词（1） AOV网络图：又称为顶点活动网，是指用顶点网络图：又称为顶点活动网，是指用顶点表征各项活动、边表征活动发生先后顺序的有向图。表征各项活动、边表征活动发生先后顺序的有向图。（2） 拓扑序列：由拓扑序列：由AOV网构造的网构造的线性序列线性序

14、列。（3） 拓扑排序：构造拓扑序列的过程。拓扑排序：构造拓扑序列的过程。2. 构造拓扑序列的步骤构造拓扑序列的步骤step1: 输出输出入度入度为零的节点；为零的节点；step2: 划去从该节点引出的所有箭线；划去从该节点引出的所有箭线；step3: 重复重复step1step2，直到输出完最后一个节点。，直到输出完最后一个节点。例：（例：（09.4）写出下列）写出下列AOV网的所有拓扑排序序列网的所有拓扑排序序列step1:输出输出入度入度为零的为零的节点；节点；step2:划去从该节点引出的划去从该节点引出的所有箭线；所有箭线；表表11-1是某工厂机床检修工序示例是某工厂机床检修工序示例顺

15、序号工序代号工序名称紧前工序1A拆卸无2B机件检查A3C电器检查A4D零件修复B5E零件加工B6F组装C、D、E7G试车F例例11-5 有六项任务，每项任务要求的前驱活动如下：有六项任务，每项任务要求的前驱活动如下：C1： C2， C5， C6C2： C3， C6C3： C4C4：无：无C5：C4，C6C6：C3，C43. 拓扑排序小结拓扑排序小结（1）拓扑排序只能针对有向无环图进行；）拓扑排序只能针对有向无环图进行；（2）一个确定的）一个确定的AOV网，其拓扑序列不是唯一的。网，其拓扑序列不是唯一的。人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自