第1页:第七章 图
第七章 图
- 7.1 图的数学基础与基本概念
- 7.2 图的存储表示
- 7.3 图的遍历
- 7.4 图的连通性
- 7.5 图的最短路径
- 7.6 拓扑排序
- 7.7 小结
第2页:图的数学基础与基本概念
7.1 图的数学基础与基本概念
- 图 G 由顶点集合 V 与顶点之间连接(边)的集合 E 组成。
- 边表示顶点之间的无序连接时为无向图;表示有序连接时为有向图。
- 无向图中若 vi 与 vj 之间存在路径,则称两顶点连通;任意两顶点都连通的图称为连通图,极大连通子图称为连通分量。
- 有向图中任意两顶点之间都存在路径时称为强连通图,其极大强连通子图为强连通分量。
- 边带有权值的图称为加权图,或称为网。
第3页:图的存储表示
7.2 图的存储表示:图无法用简单的顺序结构表示,常用的存储表示有四种:
第4页:邻接矩阵
7.2.1 邻接矩阵:图 G = (V, E) 是顶点集 V 上的二元关系,可用矩阵表示。设 V = {v1, v2, ..., vn},用矩阵 A = (aij)n×n 表示:
- aij = 1,当 (vi, vj) ∈ E;
- aij = 0,当 (vi, vj) ∉ E。
称 A 为 G 的邻接矩阵。若 G 是无向图,则 A 必为对称矩阵。
第5页:邻接矩阵中顶点度的计算
邻接矩阵上度的计算
- 无向图中,顶点 vi 的度是邻接矩阵第 i 行(或第 i 列)元素之和。
- 有向图中,顶点 vi 的出度是第 i 行元素之和,入度是第 i 列元素之和。
- 网的邻接矩阵可定义为:aij = wij((vi, vj) ∈ E);aij = ∞((vi, vj) ∉ E)。
第6页:邻接表
7.2.2 邻接表:邻接表是图的一种链式存储结构。
- 每个顶点用一个顶点结点表示,其中 data 域存放顶点信息,firstedge 是指向依附于该顶点第一条边的指针;所有顶点结点通常以一维数组顺序存储。
- 对每个顶点建立一个单链表,链表中每个边结点表示依附于该顶点的一条边,其 adjvex 域存放该边另一端的顶点序号,data 域存放边的信息,nextedge 指向下一条边。
- 顶点结点中的 firstedge 实际上就是该单链表的头指针。
第7页:十字链表
7.2.3 十字链表:十字链表是有向图的链式存储结构,每个顶点与每条边各用一个结点表示。
- 边结点含五个域:起点域 startvex、终点域 endvex 分别表示该边的起止顶点;slink 指向起点相同的下一条边,elink 指向终点相同的下一条边;data 存放边的信息。
- 顶点结点含三个域:firstoutedge 指向以该顶点为起点的第一条边,firstinedge 指向以该顶点为终点的第一条边,data 存放顶点信息。
- 顶点结点用一维数组顺序存储,便于随机存取;边结点在链表中的位置由建表过程决定,与顶点序号无关。
第8页:邻接多重表
7.2.4 邻接多重表:邻接多重表是对无向图邻接表表示的改进,每条边只用一个边结点表示。
- 边结点含六个域:mark 为标志域,用于标记该边是否被访问过;vertex1、vertex2 为该边两个顶点在图中的位置;link1 指向下一条与 vertex1 相连的边,link2 指向下一条与 vertex2 相连的边;data 存放边的信息。
- 顶点结点含 data 与 firstedge 两个域,firstedge 指向第一条与该顶点相连的边结点。
- 由于无向图边的两个顶点地位等价,顶点结点中只需一个指针域;每个边结点同时链接在两个顶点所指的边链表中。
第9页:图的遍历
7.3 图的遍历:图的遍历是图的基本操作,指按照图的结构,从图中任一顶点出发访问图中的所有顶点,且对每个顶点仅访问一次。
第10页:宽度优先遍历
7.3.1 宽度优先遍历:从任一顶点出发,先访问该顶点,再访问与之相邻且尚未访问过的所有顶点,然后分别从这些邻接顶点出发继续遍历,直至图中已被访问顶点的邻接点都被访问过;若图中尚有未访问顶点,则另选起点继续。
- 宽度优先遍历实际上是一个按层次遍历的过程,下一个被访问顶点的选择按离当前顶点由近而远进行。
- 需为每个顶点附设访问标识,已标识访问过的顶点不再从它出发遍历。
- 为保证按宽度优先进行,还需设置一个辅助队列,按与当前顶点路径的长短安排访问次序。
第11页:深度优先遍历
7.3.2 深度优先遍历:从任一顶点出发,访问该顶点,接着依次从该顶点未被访问过的邻接点出发深度优先遍历图中其它顶点,直到与该顶点连通的顶点都被访问过;若图中尚有未访问顶点,另选起点继续,直到所有顶点都被访问过。
- 深度优先遍历可看作树的先根序遍历的推广。
- 下一个被访问顶点的选择按照深度越大越优先的原则,即在已访问顶点的未访问邻接点中选择路径最长的顶点。
- 与宽度优先遍历相同,也需要为每个顶点附设访问标识,已访问过的顶点不再从它出发遍历。
第12页:图的连通性
7.4 图的连通性:图的遍历算法可直接用于解决图的连通性问题:
第13页:无向图的连通分量
7.4.1 无向图的连通分量
- 对于连通的无向图,从任意顶点出发进行遍历都可访问到图中的所有顶点。
- 对于非连通图,需从多个顶点出发才能访遍全部顶点;从某个顶点出发只能访问到该顶点所在连通分量中的所有顶点。
- 从每个连通分量的一个顶点出发遍历图,即可求得无向图的所有连通分量。
- 每次调用宽度优先或深度优先遍历算法得到的顶点访问序列,恰好就是图的各个连通分量的顶点集;这些顶点集分别加上依附于它们的边,就构成了非连通图的连通分量。
第14页:无向图的生成树
7.4.2 无向图的生成树:连通图 G 的生成树是包含 G 全部顶点、却仅含足以构成一棵树的 n-1 条边(不含任何回路)的子图。
- 从连通图任一顶点出发进行宽度或深度优先遍历,将边集 E(G) 分为两个集合:遍历中访问过的边集 T(G) 与剩余的边集 R(G)。
- T(G) 加上图中所有顶点即为 G 的极小连通子图,也就是 G 的一棵生成树。
- 遍历只对每个顶点访问一次,故访问过的边不会出现回路。
- 由宽度优先遍历得到的称为宽度优先生成树,由深度优先遍历得到的称为深度优先生成树;非连通图各连通分量的生成树构成生成森林。
第15页:最小生成树与Kruskal算法
7.4.3 最小生成树:若无向连通图是一个网,则其所有生成树中必有一棵树的边权值之和最小,称为最小代价生成树,简称最小生成树。
- 构造 n 个顶点的网的最小生成树有两个要求:必须有 n-1 条边连接网的 n 个顶点;尽可能选择权值最小的边。
- Kruskal 算法:设最小生成树为 T,T 的初始状态含 G 中 n 个顶点但无边;按 G 中边权值从小到大的次序考察各条边,若被考察的边不与 T 中已有边构成回路则放入 T,否则舍弃,直到 T 中所有顶点都被选入(或选入边数达到 n-1)为止。
第16页:图的最短路径与Dijkstra算法
7.5 图的最短路径:最短路径问题是在图中寻找两个顶点之间路径长度最短的那一条,可分为两个子问题:
- 求一个源点到其余各个顶点的最短路径;
- 求每一对顶点之间的最短路径,可反复求解子问题 1 得到。
Dijkstra 算法:按路径长度逐步递增的次序产生最短路径。设有向网 G = (V, E),源点 v0,用向量 Length 记录 v0 到各顶点的当前最短路径长度:
- 初始状态:若存在边 (v0, vi),则 Length[i] 为该边权值,否则为 ∞。
- 第一条最短路径满足 Length[i] = Min{Length[j] | vj ∈ V},即为 (v0, vi)。
- 次短路径的终点 vk 要么与源点直连,即 (v0, vk);要么是中间经过 vi 的路径 (v0, vi, vk),取两者中较短者。依次类推可求出其余最短路径。
第17页:拓扑排序
7.6 拓扑排序:可用有向无环图 DAG 表示流程图,顶点表示活动,边表示活动间的优先关系;若 (vi, vj) 是一条边,则 vi 是 vj 的直接前驱,vj 是 vi 的直接后继。
- 拓扑排序是将 DAG 中所有顶点排成一个线性序列,使得对任意 (vi, vj) ∈ E(G),vi 在线性序列中都出现在 vj 之前,该序列称为拓扑序列。
- 若图中所有顶点都在拓扑有序序列中,则该图必定不存在环,因此拓扑排序也可用于判断图中是否有环。
- 基本思想:(1)在有向图中选一个没有前驱的顶点并输出;(2)从图中删除该顶点和所有以它为起点的边;循环执行直到全部顶点输出,或当前图中不存在无前驱的顶点(说明存在有向环,排序失败)。
第18页:第七章小结
7.7 小结
- 图的基本概念
- 图的几种不同存储结构及其上的基本算法
- 图的两种不同遍历策略,以及递归与非递归算法的实现
- 在遍历基础上解决图的连通性问题的算法
- 图的两种重要应用:求图的最短路径、拓扑排序