图 数据结构.ppt

2020 1 16 1 图 专题 2012年11级新队员暑假ACM培训 主讲 廖枝平 2020 1 16 2 1 了解图的定义和术语 2 掌握图的各种存储结构 3 掌握图的深度优先搜索和广度优先搜索遍历算法 4 理解最小生成树 最短路径 拓扑排序等图的常用算法 图 专题学习导读 主要介绍图的基本概念 图的存储结构和有关图的一些常用算法 学习目的 2020 1 16 3 集合 数据元素间的关系是同属一个集合 线性结构 结点间的关系是线性关系 除开始结点和终端结点外 每个结点只有一个直接前趋和直接后继 树形结构 结点间的关系实质上是层次关系 同层上的每个结点可以和下一层的零个或多个结点 即孩子 相关 但只能和上一层的一个结点 即双亲 相关 根结点除外 图 Graph 结构 对结点 图中常称为顶点 的前趋和后继个数不加限制的 即结点之间的关系是任意的 图是一种较线性表和树更为复杂的非线性结构 是对结点的前趋和后继个数不加限制的数据结构 用来描述元素之间 多对多 的关系 2020 1 16 4 2020 1 16 5 7 1 1图的定义图是由一个顶点集V和一个弧集R构成的数据结构 Graph V R V x x 某个数据对象 是顶点的有穷非空集合 R 边的有限集合R x y x y V 无向图或R x y V Path x y 有向图是顶点之间关系的有穷集合 也叫做边 edge 集合 Path x y 表示从x到y的一条单向通路 它是有方向的 x弧尾 y弧头 7 1图及其基本运算 2020 1 16 6 有向图与无向图有向图中 边用表示 且x与y是有序的 a 有向图中的边称为 弧 b x 弧尾或初始点y 弧头或终端点无向图 边用 x y 表示 且顶x与y是无序的 完全图在具有n个顶点的有向图中 最大弧数为n n 1 在具有n个顶点的无向图中 最大边数为n n 1 2顶点的度无向图 与该顶点相关的边的数目有向图 入度ID v 以该顶点为头的弧的数目出度OD v 以该顶点为尾头的弧的数目在有向图中 顶点的度等于该顶点的入度与出度之和 2020 1 16 7 图7 1无向图和有向图 2020 1 16 8 在图7 1中 图 a 为无向图 其中G1的顶点集合和边集合分别为 V G1 1 2 3 4 5 6 7 E G1 1 2 l 3 2 3 3 4 3 5 5 6 5 7 图 c 为有向图 其中G3的顶点集合和弧集合分别为V G3 1 2 3 4 5 6 E G3 2020 1 16 9 7 1 2图的基本术语1 顶点的度与顶点v相关的边或弧的数目称作顶点v的度 在有向图中 一个顶点依附的弧头数目 称为该顶点的入度 一个顶点依附的弧尾数目 称为该顶点的出度 某个顶点的入度和出度之和称为该顶点的度 例如图7 1中 无向图G1中顶点3的度为4 顶点5的度为3 例如在图7 1中 有向图G3中顶点1的出度OD 1 3 入度ID 1 1 其度TD 1 4 2020 1 16 10 2 路径和回路在无向图G中 若存在一个顶点序列Vp Vi1 Vi2 Vin Vq 使得 Vp Vi1 Vi1 Vi2 Vin Vq 均属于E G 则称顶点Vp到Vq存在一条路径 若一条路径上除起点和终点可以相同外 其余顶点均不相同 则称此路径为简单路径 起点和终点相同的路径称为回路 简单路径组成的回路称为简单回路 路径长度路径上经过的边的数目称为该路径的路径长度 非带权图的路径长度是指此路径上边 弧的条数 带权图的路径长度是指路径上各边 弧的权之和 2020 1 16 11 简单路径若路径上各顶点v1 v2 vm均不互相重复 则称这样的路径为简单路径 回路若路径上第一个顶点v1与最后一个顶点vm重合 则称这样的路径为回路或环 2020 1 16 12 3 边和弧边 无向图中顶点的偶对 写成 Vx Vy 或 Vy Vx 弧 有向图中顶点的偶对 Vx Vy 表示从Vx到Vy 弧头 弧的终点弧尾 弧的起点 弧 Vx Vy 弧尾Vx弧头Vy 2020 1 16 13 4 子图设有两个图G V E 和G V E 若V V且E E 则称图G 是图G的子图 2020 1 16 14 图7 3连通分量和强连通分量 5 连通性在无向图中 若从顶点v1到顶点v2有路径 则称顶点v1与v2是连通的 如果图中任意一对顶点vi和vj vi vj V 都是连通的 则称此图是连通图 非连通图的极大连通子图叫做连通分量 图7 1中G1是连通图 G2是非连通图 G2中有3个连通分量 如图7 3 a 所示 6 强连通图与强连通分量在有向图中 若对于每一对顶点vi和vj 都存在一条从vi到vj和从vj到vi的路径 则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 2020 1 16 15 7 网络权某些图的边或弧具有与它相关的数 称之为权 权可以代表一个顶点到另一个顶点的距离 耗费等 网络这种带权连通图图一般称为网络 如图7 4所示 2020 1 16 16 8 生成树 生成森林生成树 一个连通图的生成树是它的极小连通子图 在n个顶点的情形下 有n 1条边 生成树是对连通图而言的是连通图的极小连通子图包含图中的所有顶点有且仅有n 1条边非连通图的生成树则组成一个生成森林 若图中有n个顶点 m个连通分量 则生成森林中有n m条边 2020 1 16 17 7 1 3图的基本运算图的基本运算也包括查找 插入和删除 1 顶点定位运算确定顶点v在图中的位置 2 取顶点运算求取图中第i个顶点 3 求第一个邻接点运算求图中顶点v的第一个邻接点 4 求下一个邻接点运算已知w为图中顶点v的某个邻接点 求顶点w的下一个邻接点 5 插入顶点运算在图中增添一个顶点v作为图的第n 1个顶点 其中n为插入该顶点前图的顶点个数 6 插入弧运算在图中增添一条从顶点v到顶点w的弧 7 删除顶点运算从图中删除顶点v以及所有与顶点v相关联的弧 8 删除弧运算从图中删除一条从顶点v到顶点w的弧 2020 1 16 18 7 2 1邻接矩阵邻接矩阵 AdjacencyMatrix 是表示顶点之间相邻关系的矩阵 设G V E 是具有n个顶点的图 则G的邻接矩阵是具有如下性质的n阶方阵 7 2图的存储结构 无向图的邻接矩阵是以主对角线对称的 有向图的邻接矩阵可能是不对称的 在有向图中 第i行1的个数就是顶点i的出度 第j列1的个数就是顶点j的入度 在无向图中 第i行 列 1的个数就是顶点i的度 2020 1 16 19 图7 6有向图及其邻接矩阵 图7 5无向图及其邻接矩阵 2020 1 16 20 对于无向图 vi vj 和 vj vi 表示同一条边 因此 在邻接矩阵中Aij Aji 无向图的邻接矩阵是 关于主对角线 对称矩阵 可用主对角线以上 或以下 的部分表示 对有向图 弧和表示方向不同的两条弧 Aij和Aji表示不同的弧 所以有向图的邻接矩阵一般不具有对称性 邻接矩阵表示法适合于以顶点为主的运算 2020 1 16 21 对于有向图 顶点vi的出度OD vi 等于邻接矩阵第i行元素之和 顶点vi的入度ID vi 等于邻接矩阵第i列元素之和 即 对于无向图 顶点vi的度等于邻接矩阵第i行的元素之和 即 OD vi ID vi TD vi 对于带权图的邻接矩阵 定义为 2020 1 16 22 无向图的邻接矩阵 2020 1 16 23 有向图的邻接矩阵 2020 1 16 24 顶点表 一个记录各个顶点信息的一维数组 邻接矩阵 一个表示各个顶点之间的关系 边或弧 的二维数组 使用邻接矩阵存储结构 可用一维数组表示图的顶点集合 用二维数组表示图的顶点之间关系 边或弧 的集合 数据类型定义如下 defineMAX VERTEX NUM20 最大顶点数typedefintAdjMatrix MAX VERTEX NUM MAX VERTEX NUM 邻接矩阵类型typedefstruct VertexTypevexs MAX VERTEX NUM 顶点表AdjMatrixarcs 邻接矩阵intvexnum arcnum 图的顶点数和弧数 MGraph 由于一般图的边或弧较少 其邻接矩阵的非零元素较少 属稀疏矩阵 因此会造成一定存储空间的浪费 2020 1 16 25 建立邻接矩阵算法 voidCreateMGraph MGraph j LocateVex G v2 G arcs i j w G arcs j i w return 2020 1 16 26 voidPrintMGraph MGraphG 输出 inti j printf OutputVertices printf s G vexs printf n printf OutputAdjMatrix n for i 0 i G vexnum i for j 0 j G vexnum j printf 4d G arcs i j printf n return 2020 1 16 27 7 2 2邻接表图的链式存储结构1 为每个顶点建立一个单链表 2 第i个单链表中包含顶点Vi的所有邻接顶点 邻接表是图的一种链式存储结构 类似于树的孩子链表表示法 在邻接表中为图中每个顶点建立一个单链表 用单链表中的一个结点表示依附于该顶点的一条边 或表示以该顶点为弧尾的一条弧 称为边 或弧 结点 2020 1 16 28 把同一个顶点发出的边链接在同一个边链表中 链表的每一个结点代表一条边 叫做表结点 边结点 邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 链域nextarc存放指向同一链表中下一个表结点的指针 数据域info存放边的权 边链表的表头指针存放在头结点中 头结点以顺序结构存储 其数据域data存放顶点信息 链域firstarc指向链表中第一个顶点 2020 1 16 29 带权图的边结点中info保存该边上的权值 顶点Vi的边链表的头结点存放在下标为i的顶点数组中 在邻接表的边链表中 各个边结点的链入顺序任意 视边结点输入次序而定 设图中有n个顶点 e条边 则用邻接表表示无向图时 需要n个顶点结点 2e个边结点 用邻接表表示有向图时 若不考虑逆邻接表 只需n个顶点结点 e个边结点 建立邻接表的时间复杂度为O n e 若顶点信息即为顶点的下标 则时间复杂度为O n e 2020 1 16 30 有向图的邻接表和逆邻接表 在有向图的邻接表中 第i个链表中结点的个数是顶点Vi的出度 在有向图的逆邻接表中 第i个链表中结点的个数是顶点Vi的入度 2020 1 16 31 图7 7为图7 6 a 的的邻接表和逆邻接表 图7 7有向图的邻接表和逆邻接表 7 6 a 2020 1 16 32 网络 带权图 的邻接表 2020 1 16 33 无向图 有向图 2020 1 16 34 无向图的邻接表 2020 1 16 35 有向图的邻接表 2020 1 16 36 存储表示typedefstructArcNode intadjvex structArcNode nextarc intinfo ArcNode 边结点类型typedefstructVNode VertexTypedata ArcNode firstarc VNode AdjList MAX VERTEX NUM typedefstruct AdjListvertices 邻接表intvexnum arcnum ALGraph 2020 1 16 37 intLocateVex ALGraphG charu inti for i 0 i G vexnum i if u G vertices i data returni if i G vexnum printf Erroru n exit 1 return0 voidCreateALGraph adjlist ALGraph 2020 1 16 38 printf InputArcs v1 v2 2020 1 16 39 7 2 3十字链表十字链表 OrthogonalList 是有向图的另一种链式存储结构 可看作是将有向图的邻接表和逆邻接表结合的一种链表 在十字链表中 为每个顶点vi设置一个结点 它包含数据域data和两个链域firstout firstin 称为顶点结点 数据域data用于存放顶点vi的有关信息 链域firstin指向以顶点vi为弧头的第一个弧结点 链域firstout指向以顶点vi为弧尾的第一个弧结点 弧结点包括四个域 尾域tailvex 头域headvex 链域hlink和tlink hlink指向弧头相同的下一条弧 tlink指向弧尾相同的下一条弧 data顶点信息 firstin以该顶点为头的第一个弧结点 firstout以该结点为尾的第一个弧结点 顶点结点 弧结点 2020 1 16 40 图7 8十字链表 图7 8为图7 6 a 有向图的十字链表 采用十字链表表示有向图 很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧 因此顶点的出度 入度都很容易求得 2020 1 16 41 十字链表的数据类型定义如下 defineMAXVtypedefstruct 弧结点 inttailvex headvex 弧尾和弧头顶点位置structArcNode hlink tlink 弧头相同和弧尾相同的弧的链域 ArcNode typedefstruct 顶点结点 VertexTypedata 顶点信息ArcNode firstin firstout 分别指向该顶点的第一条入弧和出弧 VexNode 2020 1 16 42 7 2 4邻接多重表邻接多重表是无向图的另一种链式存储结构 在邻接多重表中设置一个边结点表示图中的一条边 边结点包含五个域 结构如下所示 其中 mark域标志域 用于对该边进行标记 ivex域存放该边依附的一个顶点vi的位置信息 ilink域该链域指向依附于顶点vi的另一条边的边结点 jvex域存放该边依附的另一个顶点vj的位置信息 jlink域该链域指向依附于顶点vj的另一条边的边结点 邻接多重表为每个顶点设置一个结点 其结构如下 2020 1 16 43 图7 9邻接多重表 图7 9为图7 5 a 无向图的邻接多重表 由邻接多重表可以看出 表示边 vi vj 的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中 实现了用一个边结点表示一个边的目的 克服了在邻接表中用两个边结点表示一个边的缺点 因此邻接多重表是无向图的一种很有效的存储结构 2020 1 16 44 邻接多重表的结点数据类型定义如下 defineMAXVtypedefstruct 边结点类型 intmark 访问标识intivex jvex 该边的两个顶点位置信息structEnode ilink jlink 分别指向依附这两个顶点的下一条边 Enode typedefstruct 顶点结点类型 VertexTypedata 顶点数据域ENode firstedge 指向第一条依附该顶点的边 Vnode 2020 1 16 45 7 3图的遍历 和树的遍历相似 若从图中某顶点出发访遍图中每个顶点 且每个顶点仅访问一次 此过程称为图的遍历 TraversingGraph 但是 在图中有回路 从图中某一顶点出发访问图中其它顶点时 可能又会回到出发点 而图中或许还有顶点没有访问到 因此 图的遍历较树的遍历更复杂 图的遍历算法是求解图的连通性问题 拓扑排序和求关键路径等算法的基础 图的遍历顺序有两种 深度优先搜索 DFS 和广度优先搜索 BFS 对每种搜索顺序 访问各顶点的顺序也不是唯一的 2020 1 16 46 7 3 1深度优先搜索 DFS 1 深度优先搜索思想深度优先搜索遍历类似于树的先序遍历 假定给定图G的初态是所有顶点均未被访问过 在G中任选一个顶点i作为遍历的初始点 则深度优先搜索递归调用包含以下操作 1 访问搜索到的未被访问的邻接点 2 将此顶点的visited数组元素值置1 3 搜索该顶点的未被访问的邻接点 若该邻接点存在 则从此邻接点开始进行同样的访问和搜索 深度优先搜索DFS可描述为 1 访问v0顶点 2 置visited v0 1 3 搜索v0未被访问的邻接点w 若存在邻接点w 则DFS w 2020 1 16 47 遍历过程 DFS在访问图中某一起始顶点v后 由v出发 访问它的任一邻接顶点w1 再从w1出发 访问与w1邻接但还没有访问过的顶点w2 然后再从w2出发 进行类似的访问 如此进行下去 直至到达所有的邻接顶点都被访问过的顶点u为止 接着 退回一步 退到前一次刚访问过的顶点 看是否还有其它没有被访问的邻接顶点 如果有 则访问此顶点 之后再从此顶点出发 进行与前述类似的访问 如果没有 就再退回一步进行搜索 重复上述过程 直到连通图中所有顶点都被访问过为止 2020 1 16 48 深度优先搜索的示例 图中可能存在回路 且图的任一顶点都可能与其它顶点相通 在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点 为了避免重复访问 可设置一个标志顶点是否被访问过的辅助数组visited 它的初始状态为0 在图的遍历过程中 一旦某一个顶点i被访问 就立即让visited i 为1 防止它被多次访问 2020 1 16 49 对上图 深度优先搜索遍历的顺序 之一 为 v1 v2 v4 v8 v5 v6 v3 v7 图7 10深度优先搜索 2020 1 16 50 深度优先搜索算法 intvisited MAX VERTEX NUM voidDFS ALGraphG intv ArcNode p printf c G vertices v data visited v 1 p G vertices v firstarc while p if visited p adjvex DFS G p adjvex p p nextarc 从第v个顶点出发DFS 2020 1 16 51 整个图的DFS遍历voidDFSTraverse ALGraphG for intv 0 v G vexnum v visited v 0 for v 0 v G vexnum v if visited v DFS G v 对于连通图 从一个顶点出发 调用DFS函数即可将所有顶点都遍历到 2020 1 16 52 7 3 2广度优先搜索 BFS 1 广度优先搜索思想广度优先搜索遍历类似于树的按层次遍历 对于无向连通图 广度优先搜索是从图的某个顶点v0出发 在访问v0之后 依次搜索访问v0的各个未被访问过的邻接点w1 w2 然后顺序搜索访问w1的各未被访问过的邻接点 w2的各未被访问过的邻接点 即从v0开始 由近至远 按层次依次访问与v0有路径相通且路径长度分别为1 2 的顶点 直至连通图中所有顶点都被访问一次 广度优先搜索的顺序不是唯一的 例如图7 10 a 连通图的广度优先搜索遍历顺序可为v1 v2 v3 v4 v5 v6 v7 v8也可为v1 v3 v2 v7 v6 v5 v4 v8 2020 1 16 53 1 广度优先搜索思想设图G的初态是所有顶点均未访问 在G中任选一顶点i作为初始点 则广度优先搜索的基本思想是 1 从图中的某个顶点V出发 访问之 并将其访问标志置为已被访问 即visited i 1 2 依次访问顶点V的各个未被访问过的邻接点 将V的全部邻接点都访问到 3 分别从这些邻接点出发 依次访问它们的未被访问过的邻接点 并使 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问 直到图中所有已被访问过的顶点的邻接点都被访问到 依此类推 直到图中所有顶点都被访问完为止 2020 1 16 54 广度优先搜索在搜索访问一层时 需要记住已被访问的顶点 以便在访问下层顶点时 从已被访问的顶点出发搜索访问其邻接点 所以在广度优先搜索中需要设置一个队列Queue 使已被访问的顶点顺序由队尾进入队列 在搜索访问下层顶点时 先从队首取出一个已被访问的上层顶点 再从该顶点出发搜索访问它的各个邻接点 广度优先搜索过程广度优先生成树 广度优先搜索的示例 2020 1 16 55 广度优先搜索过程可描述为 1 f 0 r 0 队列初始化 空队列 f 队首指针 r 队尾指针 2 访问v0 3 visited v0 1 4 insert Queue f r v0 v0进入队尾 5 whilef 0do i delete Queue f r x 队首元素出队并赋于x ii 对所有x的邻接点wifvisited w 0then a 访问w b visited w 1 c insert Queue f r w w进队列 2020 1 16 56 以邻接表为存储结构 广度优先搜索遍历算法如下 defineMAXVvoidbfs ALGraph g intv ArcNode p intqueue MAXV 定义存放队列的数组intvisited MAXV 定义存放结点的访问标志的数组intf 0 r 0 x i 队列头尾指针初始化 把队列置空for i 0 in i 访问标志数组初始化visited i 0 printf d v 访问初始顶点vvisited v 1 置已访问标记r r 1 MAXV queue r v v进队while f r 若队列不空时循环f f 1 MAXV x queuet f 出队并赋给xp g adjlist x firstarc 找与顶点x邻接的第一个顶点 2020 1 16 57 p g adjlist x firstarc 找与顶点x邻接的第一个顶点while p NULL if visited p adjvex 0 若当前邻接点未被访问 visited p adjvex l 置该顶点已被访问的标志printf d p adjvex 访问该顶点r r 1 MAXV queue r p adjvex 该顶点进队 p p nextarc 找下一个邻接点 w进队列 2020 1 16 58 算法分析 如果使用邻接表表示图 则循环的总时间代价为d0 d1 dn 1 O e 其中的di是顶点i的度 如果使用邻接矩阵 则对于每一个被访问过的顶点 循环要检测矩阵中的n个元素 总的时间代价为O n2 2020 1 16 59 7 4最小生成树 1 生成树在一个无向连通图G中 其所有顶点和遍历该图经过的所有边所构成的子图G 称做图G的生成树 一个图可以有多个生成树 从不同的顶点出发 采用不同的遍历顺序 遍历时所经过的边也就不同 例如图7 12的 b 和 c 为图7 12 a 的两棵生成树 其中 b 是通过DFS得到的 称为深度优先生成树 c 是通过BFS得到的 称为广度优先生成树 图7 12生成树 2020 1 16 60 按照生成树的定义 n个顶点的连通网络的生成树有n个顶点 n 1条边 而所有包含n 1条边及n个顶点的连通图都是无回路的树 所以生成树是连通图中的极小连通子图 由于使用不同的遍历图的方法 可以得到不同的生成树 从不同的顶点出发 也可能得到不同的生成树 如深度优先生成树 广度优先生成树在图论中 常常将树定义为一个无回路连通图 对于一个带权的无向连通图 其每个生成树所有边上的权值之和可能不同 我们把所有边上权值之和最小的生成树称为图的最小生成树 求图的最小生成树有很多实际应用 例如 通讯线路铺设造价最优问题就是一个最小生成树问题 2020 1 16 61 假设把n个城市看作图的n个顶点 边表示两个城市之间的线路 每条边上的权值表示铺设该线路所需造价 铺设线路连接n个城市 但不形成回路 这实际上就是图的生成树 而以最少的线路铺设造价连接各个城市 即求线路铺设造价最优问题 实际上就是在图的生成树中选择权值之和最小的生成树 构造最小生成树的算法有很多 下面分别介绍克鲁斯卡尔 Kruskal 算法和普里姆 Prim 算法 2020 1 16 62 算法的基本思想 假设G V E 是一个具有n个顶点的带权无向连通图 T U TE 是G的最小生成树 其中U是T的顶点集 TE是T的边集 则构造最小生成树的过程如下 1 置U的初值等于V TE的初值为空集 2 按权值从小到大的顺序依次选取图G中的边 若选取的边未使生成树T形成回路 则加入TE 若选取的边使生成树T形成回路 则将其舍弃 循环执行 2 直到TE中包含 n 1 条边为止 7 4 1克鲁斯卡尔 Kruskal 算法克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法 2020 1 16 63 应用克鲁斯卡尔算法构造最小生成树的过程 2020 1 16 64 为实现克鲁斯卡尔算法需要设置一维辅助数组E 按权值从小到大的顺序存放图的边 数组的下标取值从0到e 1 e为图G边的数目 假设数组E存放图G中的所有边 且边已按权值从小到大的顺序排列 n为图G的顶点个数 e为图G的边数 克鲁斯卡尔算法如下 defineMAXE defineMAXVtypedefstruct intvex1 边的起始顶点intvex2 边的终止顶点intweight 边的权值 Edge Voidkruskal EdgeE intn inte inti j m1 m2 sn1 sn2 k intvset MAXV for i 0 i n i 初始化辅助数组vset i i k 1 表示当前构造最小生成树的第k条边 初值为1j 0 E中边的下标 初值为0while j e 生成的边数小于e时继续循环 ml E j vex1 m2 E j vex2 取一条边的两个邻接点sn1 vset m1 sn2 vset m2 分别得到两个顶点所属的集合编号if sn1 sn2 两顶点分属于不同的集合 该边是最小生成树的一条边 2020 1 16 66 printf m1 m2 d n E j weight k 生成边数增lfor i 0 i n i 两个集合统一编号if vset i sn2 集合编号为sn2的改为sn1vset i sn1 j 扫描下一条边 如果给定带权无向连通图G有e条边 且边已经按权值递增的次序存放在数组E中 则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O e 克鲁斯卡尔算法的时间复杂度与边数e有关 该算法适合于求边数较少的带权无向连通图的最小生成树 2020 1 16 67 7 4 2普里姆 Prim 算法普里姆算法的基本思想 普里姆算法是另一种构造最小生成树的算法 它是按逐个将顶点连通的方式来构造最小生成树的 从连通网络N V E 中的某一顶点u0出发 选择与它关联的具有最小权值的边 u0 v 将其顶点加入到生成树的顶点集合U中 以后每一步从一个顶点在U中 而另一个顶点不在U中的各条边中选择权值最小的边 u v 把该边加入到生成树的边集TE中 把它的顶点加入到集合U中 如此重复执行 直到网络中的所有顶点都加入到生成树顶点集合U中为止 2020 1 16 68 摘自严蔚敏版 数据结构 C语言版 P174 假设G V E 是一个具有n个顶点的带权无向连通图 T U TE 是G的最小生成树 其中U是T的顶点集 TE是T的边集 则构造G的最小生成树T的步骤如下 1 初始状态 TE为空 U v0 v0 V 2 在所有u U v V U的边 u v E中找一条代价最小的边 u v 并入TE 同时将v 并入U 重复执行步骤 2 n 1次 直到U V为止 在普里姆算法中 为了便于在集合U和 V U 之间选取权值最小的边 需要设置两个辅助数组closest和lowcost 分别用于存放顶点的序号和边的权值 对于每一个顶点v V U closest v 为U中距离v最近的一个邻接点 即边 v closest v 是在所有与顶点v相邻 且其另一顶点j U的边中具有最小权值的边 其最小权值为lowcost v 即lowcost v cost v closest v 2020 1 16 70 采用邻接表作为存储结构 设置一个辅助数组closedge lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值 adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点最近 即权值最小 2020 1 16 71 若选择从顶点0出发 即u0 0 则辅助数组的两个域的初始状态为 然后反复做以下工作 在closedge i 中选择adjvex 0 lowcost最小的边i用k标记它 则选中的权值最小的边为 closedge k G vexs k 相应的权值为closedge k lowcost 将closedge k adjvex改为0 表示它已加入生成树顶点集合 将边 closedge k G vexs k 加入生成树的边集合 2020 1 16 72 取lowcost i min lowcost i G arcs k i 即用生成树顶点集合外各顶点i到刚加入该集合的新顶点k的距离G arcs k i 与原来它们到生成树顶点集合中顶点的最短距离lowcost i 做比较 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离 如果生成树顶点集合外顶点i到刚加入该集合的新顶点k的距离比原来它到生成树顶点集合中顶点的最短距离还要近 则修改adj adjvex v 表示生成树外顶点i到生成树内顶点k当前距离最近 2020 1 16 73 利用普里姆算法建立最小生成树 typedefintVRType struct VertexTypeadjvex VRTypelowcost closedge MAX VERTEX NUM voidMiniSpanTree PRIM MGraphG VertexTypeu intk j i minCost k LocateVex G u for j 0 j G vexnum j if j k closedge j adjvex u closedge j lowcost G arcs k j closedge k lowcost 0 for i 1 i G vexnum i k minimum closedge minCost INFINITY for j 0 j G vexnum j if closedge j lowcost minCost 2020 1 16 75 普里姆算法中的第二个for循环语句频度为n 1 其中包含的两个内循环频度也都为n 1 因此普里姆算法的时间复杂度为O n2 普里姆算法的时间复杂度与边数e无关 该算法更适合于求边数较多的带权无向连通图的最小生成树 2020 1 16 76 7 5最短路径 交通网络中常常提出这样的问题 从甲地到乙地之间是否有公路连通 在有多条通路的情况下 哪一条路最短 交通网络可用带权图来表示 顶点表示城市名称 边表示两个城市有路连通 边上权值可表示两城市之间的距离 交通费或途中所花费的时间等 求两个顶点之间的最短路径 不是指路径上边数之和最少 而是指路径上各边的权值之和最小 另外 若两个顶点之间没有边 则认为两个顶点无通路 但有可能有间接通路 从其它顶点达到 路径上的开始顶点 出发点 称为源点 路径上的最后一个顶点称为终点 并假定讨论的权值不能为负数 2020 1 16 77 最短路径 如果从图中某一顶点 称为源点 到达另一顶点 称为终点 的路径可能不止一条 如何找到一条路径使得沿此路径上各边上的权值总和达到最小 对于带权的图 通常把一条路径上所经过边或弧上的权值之和定义为该路径的路径长度 从一个顶点到另一个顶点可能存在着多条路径 把路径长度最短的那条路径称为最短路径 其路径长度称为最短路径长度 无权图实际上是有权图的一种特例 我们可以把无权图的每条边或弧的权值看成是l 每条路径上所经过的边或弧数即为路径长度 本章讨论两种最常见的最短路径问题 2020 1 16 78 问题解法边上权值非负情形的单源最短路径问题 Dijkstra算法所有顶点之间的最短路径 Floyd算法 边上权值非负情形的单源最短路径问题问题的提法 给定一个带权有向图D与源点v 求从v到D中其它顶点的最短路径 限定各边上的权值大于或等于0 为求得这些最短路径 Dijkstra提出按路径长度的递增次序 逐步产生最短路径的算法 首先求出长度最短的一条最短路径 再参照它求出长度次短的一条最短路径 依次类推 直到从顶点v到其它各顶点的最短路径全部求出为止 2020 1 16 79 7 5 1求一顶点 单源点 到其余顶点的最短路径单源点最短路径是指 给定一个出发点 单源点 和一个有向网G V E 求出源点到其它各顶点之间的最短路径 迪杰斯特拉 Dijkstra 在做了大量观察后 首先提出了按路径长度递增产生各顶点的最短路径算法 我们称之为迪杰斯特拉算法 算法的基本思想 设置并逐步扩充一个集合S 存放已求出其最短路径的顶点 则尚未确定最短路径的顶点集合是V S 其中V为网中所有顶点集合 按最短路径长度递增的顺序逐个以V S中的顶点加到S中 直到S中包含全部顶点 而V S为空 2020 1 16 80 具体做法 设源点为Vl 则S中只包含顶点Vl 令W V S 则W中包含除Vl外图中所有顶点 Vl对应的距离值为0 W中顶点对应的距离值是这样规定的 若图中有弧则Vj顶点的距离为此弧权值 否则为 一个很大的数 然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中 每往S中加入一个顶点Vm 就要对W中的各个顶点的距离值进行一次修改 若加进Vm做中间顶点 使 的值小于值 则用 代替原来Vj的距离 修改后再在W中选距离值最小的顶点加入到S中 如此进行下去 直到S中包含了图中所有顶点为止 2020 1 16 81 图7 16带权有向图 设G V E 是一个带权有向图 指定的顶点v0为源点 求v0到图的其余各顶点的最短路径 如图7 16所示 若以顶点0为v0 它到其余各顶点的最短路径分别为 顶点0顶点1 无路径顶点0顶点2 最短路径为 0 2 最短路径长度为10顶点0顶点4 最短路径为 0 4 最短路径长度为30顶点0顶点3 最短路径为 0 4 3 最短路径长度为50顶点0顶点5 最短路径为 0 4 3 5 最短路径长度为60 2020 1 16 82 从以上图7 16的最短路径可以看出 1 最短路径并不一定是经过边或弧数最少的路径 如从顶点0到顶点5的路径 0 5 长度为100 路径 0 4 5 长度为90 路径 0 2 3 5 长度为70 路径 0 4 3 5 长度为60 其中最短路径为 0 4 3 5 最短路径长度为60 2 这些最短路径中 长度最短的路径上只有一条弧 且它的权值在从源点出发的所有弧的权值中最小 如从源点0出发有3条弧 其中以弧的权值为最小 此时 0 2 不仅是顶点0到顶点2的一条最短路径 而且它在从源点0到其它各顶点的最短路径中长度最短 3 按照路径长度递增的次序产生最短路径 求得第二条最短路径 0 4 之后求得第三条最短路径 0 4 3 它经过已求出的第二条最短路径 0 4 到达顶点3 求得的第四条最短路径 0 4 3 5 经过已求出的第三条最短路径 0 4 3 到达顶点5 2020 1 16 83 迪杰斯特拉算法的求解过程 2020 1 16 84 图7 17迪杰斯特拉算法求最短路径过程及结果 2020 1 16 85 2020 1 16 86 Dijkstra算法可描述如下 初始化 S v0 D j arcs 0 j j 1 2 n 1 n为图中顶点个数求出最短路径的长度 D k min D i i V S S SU k 修改 D i min D i D k arcs k i 对于每一个i V S 判断 若S V 则算法结束 否则转 2020 1 16 87 狄杰斯特拉算法dijkstra 其中n为图G的顶点数 v0为源点 defineINF32767 INF表示 defineMAXVvoiddijkstra intcost MAXV intn intvO intdist MAXV path MAXV ints MAXV intmindis inti j k for i 0 i n i dist i cost vO i 距离初始化s i 0 s 初始化if cost vO i INF 路径初始化path i vO elsepath i 1 s vO 1 源点v0放入S中for i 1 i n i 重复 直到求出v0到其余所有顶点的最短路径 for i 1 i n i 重复 直到求出v0到其余所有顶点的最短路径 mindis INF k vO for j 1 j n j 从V S中选取具有最小距离的顶点vk if s j 0 输出最短路径 2020 1 16 89 通过path i 向前回推直到v0为止 可以找出从v0到顶点vi的最短路径 输出最短路径的算法dispath如下 voiddispath intdist intpath ints intn intvO inti k for i 0 i n i if s i 1 S中顶点 k i printf d到 d的最短路径为 v0 i while k v0 printf d k k path k printf d路径长度为 d n v0 dist i elseprintf d d不存在路径 n i v0 2020 1 16 90 在狄克斯特拉算法中 求一条最短路径所花费的时间 从V S中选取具有最小距离的顶点vk花费时间O n 修改V S中顶点的距离花费时间O n 输出最短路径花费时间O n 因此求出n 1条最短路径的时间复杂度为O n2 2020 1 16 91 7 5 2每对顶点之间的最短路径顶点对之间的最短路径是指 对于给定的有向网G V E 要对G中任意一对顶点有序对V W V W 找出V到W的最短距离和W到V的最短距离 解决此问题的一个有效方法是 轮流以每一个顶点为源点 重复执行迪杰斯特拉算法n次 即可求得每一对顶点之间的最短路径 总的时间复杂度为O n3 弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的算法 虽然其时间复杂度也是O n3 但其算法的形式更简单 易于理解和编程 2020 1 16 92 弗洛伊德算法仍然使用前面定义的图的邻接矩阵arcs n 1 n 1 来存储带权有向图 算法的基本思想 设置一个n n的矩阵A k 其中除对角线的元素都等于0外 其它元素a k i j 表示顶点i到顶点j的路径长度 K表示运算步骤 开始时 以任意两个顶点之间的有向边的权值作为路径长度 没有有向边时 路径长度为 当K O时 A 0 i j arcs i j 以后逐步尝试在原路径中加入其它顶点作为中间顶点 如果增加中间顶点后 得到的路径比原来的路径长度减少了 则以此新路径代替原路径 修改矩阵元素 具体做法为 2020 1 16 93 第一步 让所有边上加入中间顶点1 取A i j 与A i 1 A 1 j 中较小的值作A i j 的值 完成后得到A 1 第二步 让所有边上加入中间顶点2 取A i j 与A i 2 A 2 j 中较小的值 完成后得到A 2 如此进行下去 当第n步完成后 得到A n A n 即为我们所求结果 A n i j 表示顶点i到顶点j的最短距离 因此 弗洛伊德算法可以描述为 A 0 i j arcs i j arcs为图的邻接矩阵A k i j min A k 1 i j A k 1 i k A k 1 k j 其中k 1 2 n 2020 1 16 94 03 30 0258 041020 40125 0 K 0 03 30 0258 04102023401258 0 K 1 2020 1 16 95 摘自 算法导论 P384 2020 1 16 96 摘自 算法导论 P384 2020 1 16 97 摘自 算法导论 P385 2020 1 16 98 Floyd算法的基本思想 定义一个n阶方阵序列 D 1 D 0 D n 1 其中D 1 i j G arcs i j D k i j min D k 1 i j D k 1 i k D k 1 k j k 0 1 n 1D 0 i j 是从顶点vi到vj 中间顶点是v0的最短路径的长度 D k i j 是从顶点vi到vj 中间顶点的序号不大于k的最短路径长度 D n 1 i j 是从顶点vi到vj的最短路径长度 2020 1 16 99 Floyd算法允许图中有带负权值的边 但不许有包含带负权值的边组成的回路 本章给出的求解最短路径的算法不仅适用于带权有向图 对带权无向图也可以适用 因为带权无向图可以看作是有往返二重边的有向图 只要在顶点vi与vj之间存在无向边 vi vj 就可以看成是在这两个顶点之间存在权值相同的两条有向边和 2020 1 16 100 弗洛伊德算法floyd如下 defineINF32767 INF表示 defineMAXVvoidfloyd intcost MAXV intn intA MAXV MAXV path MAXV MAXV inti j k for i 0 i A i k A k j 2020 1 16 101 if A i j A i k A k j A i j A i k A k j path i j k dispath A path n 输出最短路径 以下是输出最短路径的算法dispath 其中ppath 函数在path中递归输出从顶点vi到vj的最短路径 voidppath intpath MAXV inti intj intk k path i j if k 1 path i j 1时 顶点vi和vj之间无中间顶点return ppath path i k printf d k ppath path k j 2020 1 16 102 voiddispath intA MAXV intpath MAXV intn inti j for i 0 i n i for j 0 j n j if A i j INF if i j printf 从顶点 d到顶点 d没有路径 n i j else printf 从顶点 d到顶点 d路径为 i j printf d i ppath path i j printf d j printf 路径长度为 d n A i j 弗洛伊德算法包含一个三重循环 其时间复杂度为O n3 2020 1 16 103 1 拓扑排序通常我们把计划 施工过程 生产流程 程序流程等都当成一个工程 一个大的工程常常被划分成许多较小的子工程 这些子工程称为活动 这些活动完成时 整个工程也就完成了 例如 计算机专业学生的课程开设可看成是一个工程 每一门课程就是工程中的活动 图7 21给出了若干门所开设的课程 其中有些课程的开设有先后关系 有些则没有先后关系 有先后关系的课程必须按先后关系开设 如开设数据结构课程之前必须先学完程序设计基础及离散数学 而开设离散数学则必须先并行学完高等数学 程序设计基础课程 7 6拓扑排序 2020 1 16 104 图7 21课程名称及相应的课程安排次序 图7 22课程安排的AOV网 我们用一种有向图来表示课程开设 在这种有向图中 顶点表示活动 有向边表示活动的优先关系 这种有向图叫做顶点表示活动的网络 ActireOnV