数据结构-图.ppt

第7章图 数据结构 C描述 目录 7 1图的基本概念 7 2图的存储结构 7 3图的遍历 7 4图的生成树和最小生成树 7 5图的应用 7 1图的基本概念 图 Graph 是一种比线性表和树结构更复杂的数据结构 在线性表中 数据元素之间仅有线性关系 每个数据元素只有一个直接前驱和直接后继 在树形结构中 数据元素之间有着明显的层次关系结点间具有分支层次关系 每一层上的结点只能和上一层中的至多一个结点相关 但可能和下一层的多个结点相关 而在图状结构中 任意两个结点之间都可能相关 即结点之间的邻接关系可以是任意的 因此 图状结构被用于描述各种复杂的数据对象 在自然科学 社会科学和人文科学等许多领域有着非常广泛的应用 7 1 1图的定义 图 Graph 是由非空的顶点集合和一个描述顶点之间关系的边 或者弧 的集合组成 其形式化定义为 G V E V vi vi VertexType E vi vj vi vj V 其中 G表示一个图 V是图G中顶点的集合 E是图G中边的集合 集合E中 vi vj 表示顶点vi和顶点vj之间有一条直接连线 即偶对 vi vj 表示一条边 无向图G1 有向图G2 例如 对于下图中的无向图G1 对应顶点集和边集为 V G1 v1 v2 v3 v4 v5 E G1 v1 v2 v1 v4 v2 v3 v3 v4 v3 v5 v2 v5 对于下图中的有向图G2 对应顶点集和边集为 V G2 v1 v2 v3 v4 v5 E G2 7 1 2图的基本术语 有向图和无向图完全图 稠密图 稀疏图度 入度 出度子图路径连通图权和网 7 2图的存储结构 图是一种结构复杂的数据结构 表现在不仅各个顶点的度可以千差万别 而且顶点之间的逻辑关系也错综复杂 从图的定义可知 一个图的信息包括两部分 即图中顶点的信息以及描述顶点之间的关系 边或者弧 的信息 因此无论采用什么方法建立图的存储结构 都要完整 准确地反映这两方面的信息 下面介绍几种常用的图的存储结构 7 2 1邻接矩阵 1 图的邻接矩阵表示 在邻接矩阵表示中 除了存放顶点本身信息外 还用一个矩阵表示各个顶点之间的关系 若 i j E G 或 i j E G 则矩阵中第i行第j列元素值为1 否则为0 图的邻接矩阵定义为 1若 i j E G 或 i j E G A i j 0其它情形 例如 对图7 8所示的无向图和有向图 它们的邻接矩阵见图7 9 无向图 G3 G3的邻接矩阵 图 7 9 邻接矩阵表示 有向图 G4 G4 的邻接矩 图 7 9 邻接矩阵表示 2 从无向图的邻接矩阵可以得出如下结论 1 矩阵是对称的 2 第i行或第i列1的个数为顶点i的度 3 矩阵中1的个数的一半为图中边的数目 4 很容易判断顶点i和顶点j之间是否有边相连 看矩阵中i行j列值是否为1 3 从有向图的邻接矩阵可以得出如下结论 1 矩阵不一定是对称的 2 第i行中1的个数为顶点i的出度 3 第i列中1的个数为顶点i的入度 4 矩阵中1的个数为图中弧的数目 5 很容易判断顶点i和顶点j是否有弧相连 4 网的邻接矩阵表示 类似地可以定义网的邻接矩阵为 wij若 i j E G 或 i j E G A i j 0若i j 其它情形 网及网的邻接矩阵见图7 10 图 7 10 网及邻接矩阵示意图 a 网G5 b 网G5的邻接矩阵 3 图的邻接矩阵数据类型描述 用邻接矩阵表示法表示图 除了存储用于表示顶点间相邻关系的邻接矩阵外 通常还需要用一个顺序表来存储顶点信息 其形式说明如下 definen6 图的顶点数 definee8 图的边 弧 数 typedefcharvextype 顶点的数据类型 typedeffloatadjtype 权值类型 typedefstruct vextypevexs n adjtypearcs n n graph 4 建立无向图的邻接矩阵 voidcreatadj graph 初始化邻接矩阵 for k 1 k e k scanf d d 该算法的时间复杂度为O n2 5 建立有向图的邻接矩阵 voidcreatadj graph 初始化邻接矩阵 for k 1 kg arcs i j 1 该算法的时间复杂度为O n2 6 建立无向网的邻接矩阵 voidcreatadj graph 初始化邻接矩阵 for k 1 k e k scanf d d f 该算法的时间复杂度为O n2 7 建立有向网的邻接矩阵 voidcreatadj graph 初始化邻接矩阵 for k 1 k及权值wg arcs i j w 该算法的时间复杂度为O n2 7 2 2邻接表 1 图的邻接表表示 将每个结点的边用一个单链表链接起来 若干个结点可以得到若干个单链表 每个单链表都有一个头结点 所有头结点组成一个一维数组 称这样的链表为邻接表 例如 图7 8所示的无向图G3和有向图G4的邻接表见图7 11所示 b 有向图 G4 的邻接表 c 有向图 G4 的逆邻接表 图 7 11 邻接表示例 有向图 G4 a 无向图G3 b 无向图G3的邻接表 图7 11 邻接表示例 图7 11 邻接表示例 a 有向图G4 b 有向图G4的邻接表 c 有向图G4的逆邻接表 1 从无向图的邻接表可以得到如下结论 1 第i个链表中结点数目为顶点i的度 2 所有链表中结点数目的一半为图中边数 3 占用的存储单元数目为n 2e 2 从有向图的邻接表可以得到如下结论 1 第i个链表中结点数目为顶点i的出度 2 所有链表中结点数目为图中弧数 3 占用的存储单元数目为n e 从有向图的邻接表可知 不能求出顶点的入度 为此 我们必须另外建立有向图的逆邻接表 以便求出每一个顶点的入度 逆邻接表在图7 11 c 中已经给出 从该图中可知 有向图的逆邻接表与邻接表类似 只是它是从入度考虑结点 而不是从出度考虑结点 3 图的邻接表数据类型描述 图的邻接表数据类型描述如下 constintn maxn maxn表示图中最大顶点数constinte maxe maxe图中最大边数structlink 定义链表类型 elemtypedata link next structnode 定义邻接表的表头类型 elemtypev 顶点信息link next a n 1 4 无向图的邻接表建立 voidcreatlink inti j k link s for i 1 idata j s next a i next a i next s s link malloc sizeof link s data i s next a j next a j next s 该算法的时间复杂度为O n e 5 有向图的邻接表建立 voidcreatlink inti j k link s for i 1 i s link malloc sizeof link 申请一个动态存储单元s data j s next a i next a i next s 该算法的时间复杂度为O n e 6 网的邻接表的数据类型描述 网的邻接表的数据类型可描述如下 constintn maxn maxn表示网中最大顶点数constinte maxe maxe网中最大边数structlink 定义链表类型 elemtypedata floatw 定义网上的权值类型为浮点型link next structnode 定义邻接表的表头类型 elemtypev 顶点信息link next a n 1 7 无向网的邻接表建立 voidcreatlink floatw inti j k link s for i 1 i n i 建立邻接表头结点 a i v i a i next NULL for k 1 k e k scanf d d d 输入一条边 i j 及该边上的权值 s link malloc sizeof link 申请一个动态存储单元s data j s w w s next a i next a i next s s link malloc sizeof link s data i s w w s next a j next a j next s 该算法的时间复杂度为O n e 8 有向网的邻接表建立 voidcreatlink floatw inti j k link s for i 1 i及该弧上的权值 s link malloc sizeof link 申请一个动态存储单元s data j s w w s next a i next a i next s 该算法的时间复杂度为O n e 另外 请注意上面的算法中 建立的邻接表不是唯一的 与你从键盘输入边的顺序有关 输入的边的顺序不同 则得到的链表也不同 7 2 3邻接多重表 在无向图的邻接表中 每条边 Vi Vj 由两个结点表示 一个结点在第i个链表中 另一个结点在第j个链表中 当需要对边进行操作时 就需要找到表示同一条边的两个结点 这给操作带来不便 在这种情况下采用邻接多重表较方便 在邻接多重表中 每条边用一个结点表示 每个结点由五个域组成 其结点结构为 其中mark为标志域 用来标记这条边是否被访问过 i和j域为一条边的两个顶点 next1和next2为两个指针域 分别指向依附于i顶点的下一条边和j顶点的下一条边 而表头与邻接表的表头类似 邻接多重表的形式见图7 12 a 无向图 G6 b G6 的邻接多重表 图 7 12 邻接多重表示例 7 3图的遍历 图的遍历是指从图中的任一顶点出发 对图中的所有顶点访问一次且只访问一次 图的遍历操作和树的遍历操作功能相似 图的遍历是图的一种基本操作 图的许多其它操作都是建立在遍历操作的基础之上 由于图结构本身的复杂性 所以图的遍历操作也较复杂 主要表现在以下四个方面 在图结构中 没有一个 自然 的首结点 图中任意一个顶点都可作为第一个被访问的结点 在非连通图中 从一个顶点出发 只能够访问它所在的连通分量上的所有顶点 因此 还需考虑如何选取下一个出发点以访问图中其余的连通分量 在图结构中 如果有回路存在 那么一个顶点被访问之后 有可能沿回路又回到该顶点 我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过 未访问的值为0 访问过的值为1 在图结构中 一个顶点可以和其它多个顶点相连 当这样的顶点访问过后 存在如何选取下一个要访问的顶点的问题 图的遍历通常有深度优先搜索和广度优先搜索两种方式 7 3 1深度优先搜索遍历1 深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历 假定给定图G的初态是所有顶点均未被访问过 在G中任选一个顶点i作为遍历的初始点 则深度优先搜索遍历可定义如下 1 首先访问顶点i 并将其访问标记置为访问过 即visited i 1 2 然后搜索与顶点i有边相连的下一个顶点j 若j未被访问过 则访问它 并将j的访问标记置为访问过 visited j 1 然后从j开始重复此过程 若j已访问 再看与i有边相连的其它顶点 3 若与i有边相连的顶点都被访问过 则退回到前一个访问顶点并重复刚才过程 直到图中所有顶点都被访问完止 例如 对图7 13所示无向图G7 从顶点1出发的深度优先搜索遍历序列可有多种 下面仅给出三种 其它可作类似分析 在无向图G7中 从顶点1出发的深度优先搜索遍历序列举三种为 1 2 4 8 5 6 3 71 2 5 8 4 7 3 61 3 6 8 7 4 2 5 7 13 无向图 G 7 2 连通图的深度优先搜索 若图是连通的或强连通的 则从图中某一个顶点出发可以访问到图中所有顶点 否则只能访问到一部分顶点 另外 从刚才写出的遍历结果可以看出 从某一个顶点出发的遍历结果是不唯一的 但是 若我们给定图的存储结构 则从某一顶点出发的遍历结果应是唯一的 1 用邻接矩阵实现图的深度优先搜索以图7 13中无向图G7为例 来说明算法的实现 G7的邻接矩阵见图7 14 图 7 15 邻接矩阵深度优先搜索示意图 算法描述为下面形式 voiddfs inti 从顶点i出发遍历 intj printf d g vexs i 输出访问顶点visited i 1 全局数组访问标记置i表示已经访问for j 1 j n j if g arcs i j 1 用上述算法和无向图G7 可以描述从顶点1出发的深度优先搜索遍历过程 示意图见图7 15 其中实线表示下一层递归调用 虚线表示递归调用的返回 从图7 15中 可以得到从顶点1的遍历结果为1 2 4 8 5 6 3 7 同样可以分析出从其它顶点出发的遍历结果 图7 15邻接矩阵深度优先搜索示意图 2 用邻接表实现图的深度优先搜索仍以图7 13中无向图G7为例 来说明算法的实现 G7的邻接表见图7 16 7 17 邻接表深度优先搜索示意图 图7 13无向图G7 图7 16G7的邻接表 7 17 邻接表深度优先搜索示意图 算法描述为下面形式 voiddfs1 inti link p printf d a i v 输出访问顶点visited i 1 全局数组访问标记置为i表示已访问p a i next while p NULL if visited p data dfs1 p data p p next 用刚才算法及图7 16 可以描述从顶点7出发的深度优先搜索遍历示意图 见图7 17 其中实线表示下一层递归 虚线表示递归返回 箭头旁边数字表示调用的步骤 于是 从顶点7出发的深度优先搜索遍历序列 从图7 17中可得出为7 3 1 2 4 8 5 6 从其它顶点出发的深度优先搜索序列 请读者自已写出 图7 17邻接表深度优先搜索示意图 7 3 2广度优先搜索遍历1 广度优先搜索的思想 广度优先搜索遍历类似于树的按层次遍历 设图G的初态是所有顶点均未访问 在G中任选一顶点i作为初始点 则广度优先搜索的基本思想是 1 首先访问顶点i 并将其访问标志置为已被访问 即visited i 1 2 接着依次访问与顶点i有边相连的所有顶点W1 W2 Wt 3 然后再按顺序 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问 访问与W1 W2 Wt有边相连又未曾访问过的顶点 依此类推 直到图中所有顶点都被访问完为止 例如 对图7 13所示无向图G7 从顶点1出发的广度优先搜索遍历序列可有多种 下面仅给出三种 其它可作类似分析 在无向图G7中 从顶点1出发的广度优先搜索遍历序列举三种为 1 2 3 4 5 6 7 81 3 2 7 6 5 4 81 2 3 5 4 7 6 8 图7 13无向图G7 2 连通图的广度优先搜索 1 用邻接矩阵实现图的广度优先搜索遍历仍以图7 13中无向图G7及7 14所示的邻接矩阵来说明对无向图G7的遍历过程 图 7 15 邻接矩阵深度优先搜索示意图 根据该算法用及图7 14中的邻接矩阵 可以得到图7 13的无向图G7的广度优先搜索序列 若从顶点1出发 广度优先搜索序列为 1 2 3 4 5 6 7 8 若从顶点3出发 广度优先搜索序列为 3 1 6 7 2 8 4 5 从其它点出发的广度优先搜索序列可根据同样类似方法分析 voidbfs inti 从顶点i出发遍历 intQ n 1 Q为队列intf r j f r分别为队列头 尾指针f r 0 设置空队列printf d g vexs i 输出访问顶点visited i 1 全局数组标记置1表示已经访问r q r i 入队列while f r f i q f 出队列for j 1 j n j if g arcs i j 1 算法描述如下 2 用邻接表实现图的广序优先搜索遍历仍以无向图G7及图7 16所示邻接表来说明邻接表上实现广度优先搜索遍历的过程 图7 13无向图G7 图7 16G7的邻接表 7 17 邻接表深度优先搜索示意图 根据该算法及图7 16 可以得到图G7的广度优先搜索序列 若从顶点1出发 广度优先搜索序列为 1 2 3 4 5 6 7 8 若从顶点7出发 广度优先搜索序列为 7 3 8 1 6 4 5 2 从其它顶点出发的广度优先搜索序列可根据同样类似方法分析 voidBFS1 inti intq n 1 定义队列intf r link p P为搜索指针f r 0 printf d a v i visited i 1 r q r i 进队while fdata printf d a p data v visited p data 1 r q r p data p p next 算法描述如下 1 对于下图G4和G5 按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列 1 假定它们均采用邻接矩阵表示 2 假定它们均采用邻接表表示 并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的 图 G4 图 G5 图 G4 图 G5 图 G4 图 G5 图 G4 图 G5 图G4 图G5 7 4生成树和最小生成树 7 4 1基本概念1 定义 生成树 所有顶点均由边连接在一起 但不存在回路的图叫生成树 生成森林 非连通图每个连通分量的生成树一起组成非连通图的生成森林 2 特点 一个图可以有许多棵不同的生成树 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n 1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n 1条边的图不一定是生成树 通过图的遍历可以得到生成树 利用深度优先搜索遍历得到的生成树 称之为深度优先生成树 通过广度优先搜索遍历得到的 称之为广度优先生成树 对于深度优先搜索算法DFS或DFS1 由DFS i 递归到DFS j 中间必经过一条边 i j 因此 只需在DFS j 调用前输出这条边或保存这条边 即可求得生成树的一条边 整个递归完成后 则可求得生成树的所有边 对于广度优先搜索算法BFS或BFS1 若i出队 j入队 则 i j 为一条树边 因此 可以在算法的if语句中输出这条边 算法完成后 将会输出n 1条边 也可求得生成树 a 深度优先生成树 b 广度优先生成树 图 7 1 9 两种生成树示意图 7 13 无向图 G 7 4 最小生成树 对于一个连通网 假定每条边上的权均为大于零的实数 生成树不同 每棵树的权 树中所有边上的权值总和 也可能不同 权值最小的生成树称为图的最小生成树 最小生成树的概念可以应用到许多实际问题中 例如有这样一个问题 以尽可能抵的总造价建造城市间的通讯网络 把十个城市联系在一起 在这十个城市中 任意两个城市之间都可以建造通讯线路 通讯线路的造价依据城市间的距离不同而有不同的造价 可以构造一个通讯线路造价网络 在网络中 每个顶点表示城市 顶点之间的边表示城市之间可构造通讯线路 每条边的权值表示该条通讯线路的造价 要想使总的造价最低 实际上就是寻找该网络的最小生成树 构造最小生成树常用的的方法通常有两种 普里姆 Prim 算法和克鲁斯卡尔 Kruskal 算法 7 4 2普里姆算法 1 普里姆 prim 算法思想 下面仅讨论无向网的最小生成树问题 普里姆方法的思想是 在图中任取一个顶点K作为开始点 令U k W V U 其中V为图中所有顶点集 然后找一个顶点在U中 另一个顶点在W中的边中最短的一条 找到后 将该边作为最小生成树的树边保存起来 并将该边顶点全部加入U集合中 并从W中删去这些顶点 然后重新调整U中顶点到W中顶点的距离 使之保持最小 再重复此过程 直到W为空集止 求解过程参见图7 20 假设开始顶点就选为顶点1 故首先有U 1 W 2 3 4 5 6 3 1 2 4 5 6 1 4 5 5 5 3 1 2 4 5 6 4 2 1 5 5 c u 1 3 w 2 4 5 6 d u 1 3 6 w 2 4 5 e u 1 3 6 4 w 2 5 f u 1 3 6 4 2 w 5 7 4 3克鲁斯卡尔 kruskal 算法1 克鲁斯卡尔算法基本思想 克鲁斯卡尔算法的基本思想是 将图中所有边按权值递增顺序排列 依次选定取权值较小的边 但要求后面选取的边不能与前面选取的边构成回路 若构成回路 则放弃该条边 再去选后面权值较大的边 n个顶点的图中 选够n 1条边即可 例如 对图7 20 a 中无向网 用克鲁斯卡尔算法求最小生成树的过程见图7 22 a 选第 1 条边 b 选第 2 条边 a 选第 1 条边 b 选第 2 条边 a 选第1条边 b 选第2条边 图 7 22 克鲁斯卡尔方法求最小生成树的过程 e 选第5条边但不能选 1 4 边 否则会构成回路 但可选 2 3 或 5 3 之一 或者 图 7 22 克鲁斯卡尔方法求最小生成树的过程 7 5最短路径 最短路径 最短路径问题是图的又一个比较典型的应用问题 例如 某一地区的一个公路网 给定了该网内的n个城市以及这些城市之间的相通公路的距离 能否找到城市A到城市B之间一条距离最近的通路呢 如果将城市用点表示 城市间的公路用边表示 公路的长度作为边的权值 那么 这个问题就可归结为在网图中 求点A到点B的所有路径中 边的权值之和最短的那一条路径 这条路径就是两点之间的最短路径 并称路径上的第一个顶点为源点 Sourse 最后一个顶点为终点 Destination 在非网图中 最短路径是指两点之间经历的边数最少的路径 7 5 1单源点最短路径1 单源点最短路径 单源点最短路径是指 给定一个出发点 单源点 和一个有向网G V E 求出源点到其它各顶点之间的最短路径 那么怎样求出单源点的最短路径呢 我们可以将源点到终点的所有路径都列出来 然后在里面选最短的一条即可 但是这样做 用手工方式可以 当路径特别多时 显得特别麻烦 并且没有什么规律 不能用计算机算法实现 迪克斯特拉 Dijkstra 在做了大量观察后 首先提出了按路长度递增序产生各顶点的最短路径算法 我们称之为迪杰斯特拉算法 2 迪克斯特拉算法的基本思想 该算法的基本思想是 设置两个顶点的集合S和T V S 集合S中存放已找到最短路径的顶点 集合T存放当前还未找到最短路径的顶点 初始状态时 集合S中只包含源点v0 然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中 集合S每加入一个新的顶点u 都要修改顶点v0到集合T中剩余顶点的最短路径长度值 集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值 此过程不断重复 直到集合T的顶点全部加入到S中为止 Dijkstra算法的正确性可以用反证法加以证明 假设下一条最短路径的终点为x 那么 该路径必然或者是弧 v0 x 或者是中间只经过集合S中的顶点而到达顶点x的路径 因为假若此路径上除x之外有一个或一个以上的顶点不在集合S中 那么必然存在另外的终点不在S中而路径长度比此路径还短的路径 这与我们按路径长度递增的顺序产生最短路径的前提相矛盾 所以此假设不成立 3 迪杰斯特拉算法的实现 Dijkstra算法的实现 首先 引进一个辅助向量Dist 它的每个分量D i 表示当前所找到的从始点v到每个终点vi的最短路径的长度 它的初态为 若从v到vi有弧 则Dist i 为弧上的权值 否则置Dist i 为 显然 长度为 Dist j Min D i vi V 的路径就是从v出发的长度最短的一条最短路径 此路径为 v vj 那么 下一条长度次短的最短是哪一条呢 假设该次短路径的终点是vk 则可想而知 这条路径或者是 v vk 或者是 v vj vk 它的长度或者是从v到vk的弧上的权值 或者是Dist j 和从vj到vk的弧上的权值之和 依据前面介绍的算法思想 在一般情况下 下一条长度次短的最短路径的长度必是 Dist j Min Dist i vi V S 其中 D i 或者弧 v vi 上的权值 或者是D k vk S和弧 vk vi 上的权值之和 4 迪杰斯特拉算法描述 根据以上分析 可以得到如下描述的算法 1 假设用带权的邻接矩阵edges来表示带权有向图 edges i j 表示弧 vi vj 上的权值 若 vi vj 不存在 则置edges i j 为 在计算机上可用允许的最大值代替 S为已找到从v出发的最短路径的终点的集合 它的初始状态为空集 那么 从v出发到图上其余各顶点 终点 vi可能达到最短路径长度的初值为 D i edges LocateVex G v i vi V 2 选择vj 使得D j Min D i vi V S vj就是当前求得的一条从v出发的最短路径的终点 令S S j 3 修改从v出发到集合V S上任一顶点vk可达的