第7章 图09.ppt

第七章 图 7.1 图的概念 7.1.1 图的定义 图(Graph)——图G是由两个集合V和组成E`的,记为G=(V,E) 其中：V是顶点的非空有限集 E是边的有限集合，边是顶点的无序对或有序对（序偶） 有向图——有向图G是由两个集合V和E组成的 其中：V是顶点的非空有限集 E是有向边的有限集合，有向边是顶点的有序对，记为 v,w，v,w是顶点，v为起点，w为终点 无向图——无向图G是由两个集合V和E组成的 其中：V是顶点的非空有限集 E是边的有限集合，边是顶点的无序对，记为（v,w）或 （w,v)，并且（v,w)=(w,v) 7.1.2 图的基本术语 1、邻接点 2、顶点的度 图的顶点的度数之和与边数有什么关系？ 3、有向完全图：每两个顶点间都有方向相反的两条边。 n个顶点的有向完全图边数为n(n-1)。 无向完全图：每两个顶点间都有边。 n个顶点的无向完全图边数为n(n-1)/2 。 4、子图：如果图G(V,E)和图G‘(V’,E‘),满足： V’?V E’?E E’中的顶点都在V’中 则称G‘为G的子图 5、简单路径和回路 简单路径：一条路径上所有顶点均不同。 回路：一条路径前后两个端点相同。 简单回路：只有前后两个端点相同。 7.1.3 图的ADT 主要操作： 1、遍历 2、最小生成树 3、最短路径 4、拓扑序列 5、关键路径 7.2 图的存储结构 本节主要介绍和比较邻接矩阵、链接表和边集数组。 邻接矩阵——表示顶点间的关系的矩阵 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 无向图中顶点Vi的度D(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和 邻接矩阵特点 1、查找一条边的时间复杂度是0(1) 2、计算一个顶点的度的时间复杂度为0(n) 3、查找顶点v的一个邻接点w的时间复杂度0(n) 4、空间复杂度为0(n2) 5、适用于稠密矩阵 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示顶点Vi的（出边）邻接点。 特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个邻接表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立单链表，存储入边信息。 有向图的十字链表表示法 7.2.3 边集数组 利用一维数组存储图的边。 数组元素类型： struct edge{ Int fromvex; Int endvex; WeightType weight; } typedef edge edgeset[MaxEdgeNum]; 边集数组特点 1、查找边的时间复杂度? 2、计算顶点的度的时间复杂度? 3、空间复杂度为? 4、适合表示??矩阵 7.3 图的遍历 深度优先遍历(DFS) 方法：从图的某一顶点V1出发，访问此顶点；然后从V1的一个未被访问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。 DFS算法分析 1、邻接矩阵（唯一） DFS得到的顶点序列也是唯一的。 例如：图7-10中以1点为起点的DFS。 DFS:1，0，2，6，3，4，5 分析：时间复杂度为0(n2)，空间复杂度为0(n2) 2、邻接表（不唯一） DFS得到的顶点序列也是不唯一的。 若邻接表确定，DFS的顶点序列也是唯一的。 例如：图7-10中以1点为起点的DFS。若采用图7-11的邻接表。 DFS:1，6，2，0，3，5，4 分析：时间复杂度O(e)，空间复杂度O(e) BFS算法分析 1、邻接矩阵（唯一） BFS得到的顶点序列也是唯一的。 例如：图7-10中以1点为起点的BFS。 BFS:1，0，4，5，6，2，3 队列：1 0，4，5，6 4，5，6，2，3 5，6，2，3 6，2，3 2，3 3 2、邻接表（不唯一） BFS得到的顶