计算机软件基础(自考本科)(1.11).ppt

计算机 软件基础,第二篇 数据结构基础,第十一章 图,一、简单概念,1. 图的定义,（1）图G：是由一个非空有穷的顶点集合V和一个有穷的边（或弧）集合E组成。记作： G=（V，E）,（2）无向图：顶点之间的连线不具有方向性的图。,注意：有向图中，顶点之间的连线，称为弧。,注意：无向图中，顶点之间的连线，称为边。,（3）有向图：顶点之间的连线具有方向性的图。,一、简单概念,（1）完全无向图：从图中任一顶点到其余顶点，都有直接边存在的无向图。如：,1,2,3,4,5,注意：对于具有n个顶点，e条边的完全无向图：,2. 基本术语,一、简单概念,（2）完全有向图：从图中任一顶点到其余顶点，都有直接弧存在的有向图。如：,1,2,3,4,注意：对于具有n个顶点，e条边的完全有向图：,一、简单概念,（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. 用邻接矩阵存储图,（1）图的邻接矩阵：描述图中两个顶点之间邻接关系的矩阵。,（2）邻接矩阵的结构：,是一个n*n阶的方阵，其中的每一行或每一列对应于 图中的一个顶点；,一般情况下，Aij顶点的值如下：,Aij=,1：表示从顶点Vi到顶点Vj有边（或弧）,0：表示从顶点Vi到顶点Vj没有边（或弧）,二、图的存储结构,例1：写出下列无向图G1的邻接矩阵,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,1,0,0,二、图的存储结构,例2：写出下列有向图G2的邻接矩阵,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,二、图的存储结构,（3）图的邻接矩阵的性质：,1）一个图的邻接矩阵是唯一的；,2）邻接矩阵中，各行非零的个数为该行所对应顶点 的出度；各列非零的个数为该列所对应顶点的入度；,3）无向图和完全有向图的邻接矩阵是是一个对称的矩阵,二、图的存储结构,（4）建立无向图邻接矩阵的算法：,step1：输入顶点的个数n和边数e；,step2：将邻接矩阵清零；,step3：分别输入e条边的两个顶点i和j，并且令Aij=1， Aji=1。,二、图的存储结构,（4）建立无向图邻接矩阵的算法描述：,void creat ( G , A n+1 , n , e ) scanf ( “ %d “ , “ %d “ , ,二、图的存储结构,例：（09.4）设二维数组A33表示3节点无向图的邻接矩阵。编写程序，从键盘上输入邻接矩阵的数据，求出该无向图的边数以及各个节点的度数，并输出所求结果。,二、图的存储结构,解：,#include main() int a33,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)在无向图的邻接表中，各单链表表节点的个数为对应表头节点（顶点）的度；,在有向图的邻接表中，各单链表表节点的个数为对应表头节点（顶点）的出度。,三、图的遍历,1. 图的遍历,2. 深度优先遍历,深度遍历；,访问图中各节点的过程。,口诀：,小号优先；,刨根问底。,3. 广度优先遍历,广度遍历；,口诀：,小号优先；,横扫四周。,三、图的遍历,例1：（2010.4）如下图所示的无向图，分别按邻接顶点序号有小到大顺序给出广度优先遍历和深度优先遍历的顶点序列。,解：,广度优先遍历,深度优先遍历,1237456,1245637,三、图的遍历,例2：（2008.4）对于下图,解：,广度优先遍历:,（1）从顶点1出发，按邻接顶点序号由小到大的顺序给出广度优先遍历的顶点序列。,1256734,四、最小生成树无向图的应用,1. 相关概念,（1）连通图：从图中任意一点出发，都能直接或间接到达其余点的图。,（2）子图：如果图G1的所有顶点和边完全被图G包含，则称图G1为图G的子图。,（3）图的连通分量：是指所研究图的最大的连通的子图。,注意：对于连通图来说，其连通分量就是它本身。,四、最小生成树无向图的应用,2. 图的最小生成树,（1）图的生成树：指该图最小的连通的子图。,1）“最小”的含义：,一个图的生成树有n个顶点，n-1条边，如果多一条边将使生成树产生回路，少一条边将使生成树不连通,2）连通图的必要条件：,一个连通图，具有n个顶点，则至少有n-1条边。,四、最小生成树无向图的应用,例如：图a的部分生成树如b所示,结论：,一个图，可以 生成多棵树。,四、最小生成树无向图的应用,（2）最小生成树：,各边权值之和为最小的生成树。,（3）求最小生成树的方法克鲁斯卡尔法,口诀：,权值升序选边；,包含所有顶点；,禁止产生回路。,确保树木连通。,四、最小生成树无向图的应用,例： （2008.4）对于下图,（2）给出克鲁斯卡尔法构造的最小生成树。,五、拓扑排序有向图的应用,1. 有关名词,（1） AOV网络图：又称为顶点活动网，是指用顶点表征各项活动、边表征活动发生先后顺序的有向图。,（2） 拓扑序列：由AOV网构造的线性序列。,（3） 拓扑排序：构造拓扑序列的过程。,五、拓扑排序有向图的应用,2. 构造拓扑序列的步骤,step1: 输出入度为零的节点；,step2: 划去从该节点引出的所有箭线；,step3: 重复step1step2，直到输出完最后一个节点。,五、