图(数据结构(C语言版).ppt

第7章图 图是另一种非线性数据结构 是一种更为复杂的数据结构 在图中 数据元素之间是多对多的关系 即一个数据元素对应多个直接前驱元素和多个直接后继元素 图的应用领域十分广泛 如化学分析 工程设计 遗传学 人工智能等 7 1图的基本概念 7 1 1图的定义图是由顶点集合与边的集合组成的数据结构 图G的形式化定义为G V E 其中 V是图中结点 Vertices 的非空有限集合 E是图中边 Edges 的有限集合 即图的定义也可以这样表述 图是由有限个结点的集合 V 及结点与结点相连的边的集合 E 组合而成 7 1图的基本概念 如果 E 则表示从顶点x到顶点y存在一条弧 x称为弧尾或起始点 y称为弧头或终端点 这种图的边是有方向的 这样的图称为有向图 如果 E且有 E 即E是对称关系 这时用无序对 x y 代替两个有序对 表示x与y之间存在一条边 这样的图称为无向图 有向图和无向图的表示如图7 1所示 7 1图的基本概念 在图7 1中 有向图G1可以表示为G1 V1 E1 其中 顶点集合V1 A B C D 边的集合E1 无向图G2可以表示为G2 V2 E2 其中 顶点集合V2 A B C D 边的集合E2 A B A D B C B D C D 7 1图的基本概念 假设图的顶点数目是n 图的边数或者弧的数目是e 如果不考虑顶点到自身的边或弧 即如果存在弧 则vi vj 对于无向图 边数e的取值范围为0 n n 1 2 将具有n n 1 2条边的无向图称为完全图或无向完全图 对于有向图 弧度e的取值范围是0 n n 1 将具有n n 1 条弧的有向图称为有向完全图 当enlogn时 称为稠密图 7 1图的基本概念 7 1 2图的相关概念1 邻接顶点在无向图G V E 中 如果 u v 是G中的一条边 则称u和v互为邻接顶点 并称边 u v 依附于顶点u和v 在图7 1所示的无向图G2中 顶点A的邻接顶点有B和D 在有向图G V A 中 如果是G的一条弧 则称顶点u邻接到顶点v 顶点v邻接自顶点u 并称与顶点u和顶点v相关联 在图7 1所示的有向图G1中 顶点A邻接到顶点B 弧与顶点A和B相关联 7 1图的基本概念 2 顶点的度顶点v的度是指与其相关联的边的数目 记作TD v 对于有向图 顶点的度为该顶点的入度与出度之和 即TD v ID v OD v 其中 顶点v的入度ID v 是以v为终点的有向边 弧 的条数 顶点v的出度OD v 是以v为始点的有向边 弧 的条数 在图7 1所示的有向图G1中 顶点A的入度ID A 为2 顶点A的出度OD A 为3 因此 顶点A的度TD A ID A OD A 2 3 5 7 1图的基本概念 3 路径在图G V E 中 如果从顶点vi出发有一组边可到达顶点vj 则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径 在图7 1所示的无向图G2中 从顶点A到顶点C的路径为A B C或A D C 7 1图的基本概念 4 回路在路径中 如果第一个顶点与最后一个顶点相同 则这样的路径称为回路或环 在路径所经过的顶点序列中 如果顶点不重复出现 则称这样的路径为简单路径 在回路中 除了第一个顶点和最后一个顶点外 如果其他的顶点不重复出现 则称这样的回路为简单回路或简单环 7 1图的基本概念 5 子图假设存在两个图G V E 和G V E 如果G 的顶点和关系都是V的子集 即有V V E E 则G 为G的子图 如图7 2所示 7 1图的基本概念 6 连通图和强连通图在无向图中 如果从顶点vi到顶点vj存在路径 则称顶点vi到vj是连通的 如果图中的任何两个顶点之间都是连通的 则称图是连通图 无向图中的极大连通子图称为连通分量 无向图G3与连通分量如图7 3所示 7 1图的基本概念 在有向图中 如果对于任意两个顶点vi和vj 且vi vj 从顶点vi到顶点vj和顶点vj到顶点vi都存在路径 则该图称为强连通图 有向图的极大强连通子图称为强连通分量 有向图G4的强连通分量如图7 4所示 7 1图的基本概念 7 生成树一个连通图的生成树是一个极小连通子图 它含有图中的全部顶点 但只有足以构成一棵树的n 1条边 图7 3中无向图G3的最大连通分量的一棵生成树如图7 5所示 7 1图的基本概念 8 权在实际应用中 图的边或弧往往与具有一定意义的数有关 这种与边或弧相关的数称为权 权反映了这条边或弧的某种特征的数据 例如 权通常表示两个顶点之间的距离或者时间 9 网带权的图称为网 一个网如图7 6所示 7 1图的基本概念 7 1 3图的抽象数据类型1 数据对象集合图的数据对象集合为图的各个元素的集合 图分为有向图和无向图 图中结点之间的关系用弧或边表示 连接弧或边的结点称为顶点 2 基本操作集合 1 CreateGraph G 图的创建 初始条件 图G不存在 操作结果 构造一个图G 2 DestroyGraph T 销毁图 初始条件 图G存在 操作结果 销毁图G 7 1图的基本概念 3 LocateVertex G v 根据顶点值定位 初始条件 图G存在 顶点v值合法 操作结果 如果图G中存在顶点v 则返回顶点v在图G中的位置 如果图G中没有顶点v 则返回值为空 4 GetVertex G i 根据序号定位 初始条件 图G存在 操作结果 返回图G中序号i对应的顶点值 5 FirstAdjVertex G v 返回v的第一个邻接顶点 初始条件 图G存在 操作结果 返回图G中顶点v的第一个邻接顶点 如果v没有邻接顶点或图中没有顶点v 则函数返回空 7 1图的基本概念 6 NextAdjVertex G v w 返回v的下一个邻接顶点 初始条件 图G存在 w是图G中v的某个邻接顶点 操作结果 返回顶点v的下一个邻接顶点 7 InsertVertex G v 插入顶点 初始条件 图G存在 v值合法 操作结果 在图G中增加新的顶点v 图的顶点数增1 8 DeleteVertex G v 删除顶点 初始条件 图G存在 v值合法 操作结果 删除图G的顶点v及与顶点v相关联的弧 7 1图的基本概念 9 InsertArc G v w 插入弧 初始条件 图G存在 v和w合法 操作结果 在图G中增加一条从v到w的弧 10 DeleteArc G v w 删除弧 初始条件 图G存在 v和w合法 且存在弧 v w 操作结果 删除图G中从v到w的弧 11 DFSTraverseGraph G 图的深度遍历操作 初始条件 图G存在 操作结果 从某个顶点出发 按照深度优先的次序 对图G中的每个顶点访问一次且仅访问一次 7 2图的存储结构 7 2 1邻接矩阵表示法图的邻接矩阵表示法也称为数组表示法 它采用两个数组来表示图 一个是用于存储顶点信息的一维数组 一个是用于存储图中顶点之间的关联关系的二维数组 这个关联关系的数组被称为邻接矩阵 如果图是一个无权图 则图的邻接矩阵是具有以下性质的n n的矩阵 7 2图的存储结构 在图7 1中 有向图G1的弧的集合为A 无向图G2的边的集合为E A B A D B C B D C D 它们的邻接矩阵表示如图7 7所示 7 2图的存储结构 图的邻接矩阵存储结构用C语言描述如下 defineINFINITY32768 定义一个无限大的值 defineMAXVERTEX50 最大顶点个数 typedefenum DG DN UG UN GraphKind 图的类型 有向图 有向网 无向图和无向网 typedefstruct VRTypeadj 对于无权图 用1表示相邻 0表示不相邻 对于带权图 存储权值 InfoPtr info 与弧或边的相关信息 ArcNode AdjMatrix MAXVERTEX MAXVERTEX typedefstruct 图的类型定义 VertexTypevertex MAXVERTEX 顶点数组 AdjMatrixarcs 邻接矩阵 存储边或弧的信息 intvexnum arcnum 顶点数和边 弧 的数目 GraphKindkind 图的类型 MGraph 7 2图的存储结构 例7 1 采用邻接矩阵创建一个有向网N 如图7 9所示 voidCreateGraph MGraph N 采用邻接矩阵表示法创建有向网N inti j k w VertexTypev1 v2 printf 请输入有向网的顶点数 弧数 scanf d d 7 2图的存储结构 for i 0 ivexnum i 创建一个数组 用于保存网的各个顶点 scanf s N vertex i for i 0 ivexnum i 初始化邻接矩阵 for j 0 jvexnum j N arcs i j adj INFINITY N arcs i j info NULL 弧的信息初始化为空 printf 请输入 d条弧的弧尾弧头权值 以空格分隔 n N arcnum for k 0 karcnum k scanf s s d v1 v2 图的类型为有向网 7 2图的存储结构 intLocateVertex MGraphN VertexTypev 在顶点向量中查找顶点v 找到返回在向量的序号 否则返回 1 inti for i 0 i N vexnum i if strcmp N vertex i v 0 returni return 1 7 2图的存储结构 voidDestroyGraph MGraph N 销毁网N inti j for i 0 ivexnum i 释放弧的相关信息 for j 0 jvexnum j if N arcs i j adj INFINITY 如果存在弧 if N arcs i j info NULL 如果弧有相关信息 释放该信息占用的空间 free N arcs i j info N arcs i j info NULL N vexnum 0 将网的顶点数置为0 N arcnum 0 将网的弧的数目置为0 7 2图的存储结构 7 2 2邻接表表示法一个图的邻接表表示由表头结点表和边表两部分构成 1 表头结点表 表头结点采用顺序存储结构实现 这样可以随机地访问任意顶点 表头结点由两个域组成 数据域和指针域 其中 数据域用来存放顶点信息 指针域用来指向边表中的第一个结点 2 边表 边表由三个域组成 邻接点域 数据域和指针域 其中 邻接点域表示与相应的表头顶点邻接点的位置 数据域存储与边或弧的信息 指针域用来指示下一个边或弧的结点 表头结点与边表结点的存储结构如图7 11所示 7 2图的存储结构 例如 图7 1中的两个图G1和G2用邻接表表示如图7 12所示 用表头结点存储图中的各个顶点 边表存储与对应结点相关联的顶点编号 7 2图的存储结构 图的邻接表存储结构可以用C语言描述如下 defineMAXVERTEX100 最大顶点个数 typedefenum DG DN UG UN GraphKind 图的类型 有向图 有向网 无向图和无向网 typedefstructArcNode 边表结点的类型定义 intadjvex 弧指向的顶点的位置 InfoPtr info 与弧相关的信息 structArcNode nextarc 指示下一个与该顶点相邻接的顶点 ArcNode typedefstructVNode 表头结点的类型定义 VertexTypedata 用于存储顶点 ArcNode firstarc 指示第一个与该顶点邻接的顶点 VertexNode AdjList MAXVERTEX typedefstruct 图的类型定义 AdjListvertex intvexnum arcnum 图的顶点数目与弧的数目 GraphKindkind 图的类型 AdjGraph 7 2图的存储结构 有时为了方便求某个顶点的入度 需要建立一个有向图的逆邻接链表 也就是为每个顶点vi建立一个以vi为弧头的链表 图7 1所示的有向图G1的逆邻接链表如图7 13所示 7 2图的存储结构 例7 2 编写算法 采用邻接表创建图7 1中的无向图G2 voidCreateGraph AdjGraph G 采用邻接表存储结构 创建无向图G inti j k VertexTypev1 v2 定义两个顶点v1和v2 ArcNode p printf 请输入图的顶点数 边数 逗号分隔 scanf d d j为入边i为出边创建邻接表 7 2图的存储结构 p ArcNode malloc sizeof ArcNode p adjvex j p info NULL p nextarc G vertex i firstarc G vertex i firstarc p i为入边j为出边创建邻接表 p ArcNode malloc sizeof ArcNode p adjvex i p info NULL p nextarc G vertex j firstarc G vertex j firstarc p G kind UG 7 2图的存储结构 intLocateVertex AdjGraphG VertexTypev 返回图中顶点对应的位置 inti for i 0 ivertex i firstarc p指向边表的第一个结点 if p NULL 如果边表不为空 则释放边表的结点 q p nextarc free p p q G vexnum 0 将顶点数置为0 G arcnum 0 将边的数目置为0 7 2图的存储结构 7 2 3十字链表表示法十字链表 OrthogonalList 是有向图的又一种链式存储结构 实际上 它是将有向图的邻接表与逆邻接链表结合起来得到的一种链表 在十字链表中 同样包括表头结点和弧结点 弧结点包含五个域 尾域tailvex 头域headvex infor域和两个指针域hlink tlink 其中 尾域tailvex用于表示弧尾顶点在图中的位置 头域headvex表示弧头顶点在图中的位置 infor域表示弧的相关信息 指针域hlink指向弧头相同的下一条弧 tlink指向弧尾相同的下一条弧 7 2图的存储结构 有向图的十字链表存储表示如图7 15所示 有向图的十字链表存储结构用C语言描述如下 defineMAXVERTEX100 最大顶点个数 typedefstructArcNode 弧结点的类型定义 intheadvex tailvex 弧的头顶点和尾顶点位置 InfoPtr info 与弧相关的信息 struct hlink tlink 指示弧头和弧尾相同的结点 ArcNode typedefstructVertexNode 顶点结点的类型定义 VertexTypedata 用于存储顶点 ArcNode firstin firstout 分别指向顶点的第一条入弧和出弧 VertexNode typedefstruct 图的类型定义 VertexNodevertex MAXVERTEX intvexnum arcnum 图的顶点数目与弧的数目 OLGraph 7 2 4邻接多重链表表示法邻接多重链表 AdjacencyMulti list 是无向图的另一种链式存储结构 之所以提出邻接多重表是因为它能提供更为方便的边的信息 7 3图的遍历 与树类似 图也存在遍历问题 图的遍历是指从图中某个顶点出发 按照某种方法对图中每个顶点访问且仅访问一次的操作 图的遍历是求解图的连通性问题 拓扑排序和关键路径的基础 图的遍历主要有两种方式 深度优先搜索和广度优先搜索 7 3图的遍历 7 3 1图的深度优先搜索1 图的深度优先搜索的定义图的深度优先搜索 Depth FirstSearch DFS 是指按照深度方向搜索 它类似于树的先根遍历 是树的先序遍历的推广 图的深度优先搜索的思想是 1 从图中某个顶点v0出发 访问顶点v0 2 访问顶点v0的第一个邻接点 然后以该邻接点为新的顶点 访问该顶点的邻接点 重复执行以上操作 直到当前顶点没有邻接点为止 3 返回到上一个已经访问过还有未被访问的邻接点的顶点 按照以上步骤继续访问该顶点的其他未被访问的邻接点 以此类推 直到图中所有的顶点都被访问过 7 3图的遍历 图的深度优先搜索过程如图7 18所示 其中 访问顶点的方向用实箭头表示 回溯用虚箭头表示 旁边的数字表示访问或回溯的次序 7 3图的遍历 2 图的深度遍历的算法实现图的深度优先搜素 邻接表实现 的算法描述如下 intvisited MAXVERTEX 访问标志数组 voidDFSTraverse AdjGraphG 从第1个顶点起 深度优先搜索图G intv for v 0 v G vexnum v visited v 0 访问标志数组初始化为未被访问 for v 0 v G vexnum v if visited v DFS G v 对未访问的顶点v进行深度优先遍历 printf n 7 3图的遍历 voidDFS AdjGraphG intv 从顶点v出发递归深度优先搜索图G intw visited v 1 访问标志设置为已访问 Visit G vertex v data 访问第v个顶点 for w FirstAdjVertex G G vertex v data w 0 w NextAdjVertex G G vertex v data G vertex w data if visited w DFS G w 递归调用DFS访问的序号为w的邻接顶点 如果要遍历的图是一个无向连通图或者是一个强连通图 则只需要调用一次DFS G v 就可以搜素整个图 否则需要多次调用DFS G v 7 3图的遍历 以邻接表作为存储结构 查找v的第一个邻接点的算法实现如下 intFirstAdjVertex AdjGraphG VertexTypev 返回顶点v的第一个邻接顶点的序号 ArcNode p intv1 v1 LocateVertex G v v1为顶点v在图G中的序号 p G vertex v1 firstarc if p 如果顶点v的第一个邻接点存在 返回邻接点的序号 否则返回 1 returnp adjvex elsereturn 1 7 3图的遍历 以邻接表作为存储结构 查找v的相对于w的下一个邻接点的算法实现如下 intNextAdjVertex AdjGraphG VertexTypev VertexTypew 返回v的相对于w的下一个邻接顶点的序号 ArcNode p next intv1 w1 v1 LocateVertex G v v1为顶点v在图G中的序号 w1 LocateVertex G w w1为顶点w在图G中的序号 for next G vertex v1 firstarc next if next adjvex w1 next next nextarc p next p指向顶点v的邻接顶点w的结点 if p p nextarc 如果w不存在或w是最后一个邻接点 则返回 1 return 1 elsereturnp nextarc adjvex 返回v的相对于w的下一个邻接点的序号 图的非递归实现深度优先搜素的算法如下 7 3图的遍历 7 3 2图的广度优先搜索1 图的广度优先搜索的定义图的广度优先搜索 Breadth FirstSearch BFS 类似于树的层次遍历 是树的按层次遍历的推广 图的广度优先搜索的思想是 1 从图的某个顶点v0出发 首先访问顶点v0 2 依次访问顶点v0的未被访问的每一个邻接点 3 分别从这些邻接顶点出发 依次访问它们各个未被访问的邻接顶点 并保证先被访问的邻接点的邻接点先访问 后被访问的邻接点的邻接点后访问 重复执行步骤 3 直到所有顶点都被访问 图7 18给出了一个广度优先搜索的过程示意图 其中 箭头表示搜索方向 箭头旁边的数字表示搜索顺序 A为起始点 2 图的广度优先搜索的算法实现在图的广度优先的搜索过程中 同样也需要设立一个访问标志数组visited n 其初值为0 如果某个顶点被访问 则相应的分量置为1 广度优先搜索的算法描述如下 1 首先访问v0 并置访问标志为1 然后将v0入队列 2 如果队列不为空 则重复执行以下步骤 队头结点v出队列 对于v的所有邻接顶点w 如果w未被访问 则访问w并设置访问标志 然后将w入队列 图的广度优先搜索的算法实现如下 voidBFSTraverse AdjGraphG 从第1个顶点出发 按广度优先非递归搜索图G intv front rear ArcNode p intqueue MAXVERTEX 定义一个队列Q front rear 1 初始化队列Q for v 0 v G vexnum v 初始化标志位 visited v 0 v 0 visited v 1 设置访问标志为1 表示已经被访问过 Visit G vertex v data rear rear 1 MAXVERTEX queue rear v while frontadjvex 0 如果该顶点未被访问过 visited p adjvex 1 Visit G vertex p adjvex data rear rear 1 MAXVERTEX queue rear p adjvex p p nextarc p指向下一个邻接点 7 4图的应用 7 4 1图的连通性问题1 无向图的连通分量在图的遍历中 对于连通图 无论是广度优先搜索还是深度优先搜索 只需要调用一次搜索过程 即从任何一个顶点出发 都可以遍历图中的各个顶点 对于非连通图 则需要从多个顶点出发对图进行遍历 每次从新顶点开始遍历得到的序列就是图的各个连通分量的顶点集合 7 4图的应用 例如 图7 3中的非连通图G3的邻接表如图7 21所示 对图G3进行深度优先遍历 因为图G3是非连通图且有3个连通分量 需要调用3次FirstAdjVertex过程才能完成图的深度搜索 得到的序列为A B C D I EF GH 7 4图的应用 2 图中两个顶点之间的简单路径在图的应用问题中 常常需要找出从顶点u到顶点v的简单路径 从顶点u到顶点v可能存在多条简单路径 由于在遍历过程中 要访问图中的所有顶点 因此 可以在深度 或广度 优先搜索算法的基础上增加适当的条件 以得到此问题的算法 算法思想 从顶点u出发 进行深度 或广度 优先搜索 如果能搜索到顶点v 则表明从顶点u到顶点v存在一条简单路径 因为在搜索过程中 每个顶点访问且仅访问一次 所以这条路径一定是简单路径 因此 只要在搜索过程中 将搜索的路线记录下来 就得到了从顶点u到顶点v的一条简单路径 intpre MAXVERTEX voidBriefPath AdjGraphG intu intv 求连通图G中从顶点u到顶点v的一条简单路径 inti pre int malloc G vexnum sizeof int for i 0 ivexnum i pre i 1表示顶点未被访问 pre i 1 pre u u pre i 1表示顶点u已经被访问 DFS Path G u v 深度优先搜索找出一条从顶点u到顶点v的简单路径 free pre voidDFS Path GraphG intu intv 深度优先搜索图G 找出一条从顶点u到顶点v的简单路径 intj for j FirstAdjVertex G u j 0 j NextAdjVertex G u j if pre j 1 pre j u if j v 当找到顶点v时 输出顶点u到顶点v的路径 PrintPath pre v elseDFS Path G j v 3 图的生成树与最小生成树对非连通图进行深度 或广度 优先搜索 可以得到深度 或广度 优先生成树 图7 22就是对应图G6的一棵深度 广度 优先生成树 最小生成树具有以下重要的性质 假设一个连通网N V E V是顶点的集合 E是边的集合 U是V的一个非空子集 如果 u v 是一条具有最小权值的边 其中 u U v V U 那么一定存在一棵包含边 u v 的最小生成树 最小生成树的构造算法有两个 普里姆 Prim 算法和克鲁斯卡尔 Kruskal 算法 1 普里姆算法假设N V E 是连通网 TE是N的最小生成树边的集合 执行以下操作 1 初始时 令U u0 u0 V TE 2 在所有u U v V U的边中选一条代价最小的边 u0 v0 并入集合TE 同时将顶点v0并入集合U 3 重复执行步骤 2 直到U V为止 这时 边集合TE必定含有n 1条边 则T V TE 就是连通网N的最小生成树 例如 图7 23就是利用普里姆算法构造最小生成树的过程 为了实现这个算法 需要设置一个辅助数组closeedge 以记录从U到V U具有最小代价的边 对于每个顶点v V U closeedge v 记录所有与v邻接的 从U到V U的那组边中的最小边信息 closedge v 包括两个域adjvex和lowcost 其中 adjvex域记录最小边在U中的那个顶点 lowcost域存储最小边的权值 显然有 closeedge v lowcost Min cost u v u U 根据普里姆算法构造最小生成树 各个参数的变化情况如表7 1所示 普里姆算法用C语言描述如下 voidPrim MGraphG VertexTypeu 利用普里姆算法求从第u个顶点出发构造网G的最小生成树T inti j k closeedgeclosedge k LocateVertex G u k为顶点u对应的序号 for j 0 j G vexnum j 数组初始化 strcpy closedge j adjvex u closedge j lowcost G arc k j adj closedge k lowcost 0 初始时集合U只包括顶点u printf 最小代价生成树的各条边为 n for i 1 i G vexnum i 选择剩下的G vexnum 1个顶点 k MiniNum closedge G k为与U中顶点相邻接的下一个顶点的序号 printf s s n closedge k adjvex G vertex k 输出生成树的边 closedge k lowcost 0 第k顶点并入U集 for j 0 j G vexnum j if G arc k j adj closedge j lowcost 新顶点加入U集后重新将最小边存入数组 strcpy closedge j adjvex G vertex k closedge j lowcost G arc k j adj 2 克鲁斯卡尔算法克鲁斯卡尔算法的策略是 按照边的权值递增的顺序 依次考查图中的每一条边 如果当前正在考察的边边与已经选择的边不构成回路 则选择该边 重复执行这个过程 直到构成生成树为止 假设N V E 是连通网 TE是N的最小生成树 将N中的边按权值从小到大的顺序排列 构造最小生成树的步骤如下 1 初始时 TE中只有n个顶点 每个顶点自成一个分量 而TE的边的集合TE 2 当TE的边数小于n 1时 重复执行以下步骤 在连通网N的边集E中选择权值最小的边 vi vj 并从E中删除之 如果vi和vj分别落在不同的连通分量上 则将该边加入到TE中 否则丢掉该边 继续在E中选择一条权值最小的边 例如 图7 25就是利用卡鲁斯卡尔算法构造最小生成树的过程 卡鲁斯卡尔算法用C语言描述如下 voidKruskal MGraphG 克鲁斯卡尔算法构造最小生成树 intset MAXVERTEX i j inta 0 b 0 min G arc a b adj k 0 for i 0 i G vexnum i 初始时 各顶点分别属于不同的集合 set i i printf 最小生成树的各条边为 n while k G vexnum 1 查找所有最小权值的边 for i 0 i G vexnum i 在矩阵的上三角查找最小权值的边 for j i 1 j G vexnum j if G arc i j adj min min G arc i j adj a i b j min G arc a b adj INFINITY 删除上三角中最小权值的边 下次不再查找 if set a set b 如果边的两个顶点在不同的集合 printf s s n G vex a G vex b 输出最小权值的边 k for i 0 i G vexnum i if set i set b 将顶点b所在集合并入顶点a集合中 set i set a 7 4 2有向无环图有向无环图 DirectedAcyclicGraph 是指一个没有环的有向图 简称DAG 有向无环图可用来描述工程或系统的进行过程 在有向无环图描述工程的过程中 将工程分为若干个活动 即子工程 1 拓扑排序用顶点表示活动 用弧表示活动间的优先关系的有向无环图 称为顶点表示活动的网ActivityOnVertexNetwork 简称AOV网 例如 计算机科学与技术专业的必修课程及先修课程的关系可以用AOV网表示 学习这些课程的过程可以看成是一项工程 学习每一门课程可以看成是一个活动 必修课程及先修课程的关系如表7 2所示 对AOV网进行拓扑排序的基本思想如下 1 在AOV网中任意选择一个无前驱的顶点 即顶点入度为零 将该顶点输出 2 从AOV网中删除该顶点和从该顶点出发的弧 3 重复执行步骤 1 和 2 直到AOV网中不存在无前驱的结点 4 若此时输出的结点数小于有向图的顶点数 则说明有向图中存在回路 否则输出的顶点顺序即为一个拓扑序列 按照以上步骤 图7 27所示的AOV网的拓扑序列为 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 或 C6 C7 C8 C9 C1 C2 C3 C4 C5 C10 图7 28是AOV网的拓扑序列的构造过程 其拓扑序列为 V1 V2 V3 V5 V4 V6 2 关键路径有向图在工程管理中有着广泛的应用 用有向图表示工程管理时通常有两种方法 1 用顶点表示活动 用有向弧表示活动间的优先关系 即上节讨论的AOV网 2 用顶点表示事件 用弧表示活动 弧的权值表示活动所需要的时间 把用第二种方法构造的有向无环图称为边表示活动的网 ActivityOnEdgeNetwork 简称为AOE网 图7 29是一个具有10个活动 8个事件的AOE网 v1 v2 v8表示8个事件 表示10个活动 a1 a2 a10表示活动的执行时间 进入顶点的有向弧表示的活动已经完成 从顶点出发的有向弧表示的活动可以开始 顶点v1表示整个工程的开始 v8表示整个工程的结束 顶点v5表示活动a4 a5 a6已经完成 活动a7和a8可以开始 其中 完成活动a5和活动a6分别需要5天和6天 在AOE网中从源点到汇点的最长路径的长度即为完成整个工程任务所需要的时间 该路径叫做关键路径 关键路径上的活动叫做关键活动 下面介绍与关键路径有关的几个概念 1 事件vi的最早发生时间ve i 从源点到顶点vi的最长路径的长度 称为事件vi的最早发生时间 记作ve i 求解ve i 可以从源点ve 0 0开始 按照拓扑排序规则根据递推得到 ve i Max ve k dut T 1 i n 1 其中 T是所有以第i个顶点为弧头的弧的集合 dut 表示弧对应的活动的持续时间 2 事件vi的最晚发生时间vl i 在保证整个工程完成的前提下 活动必须开始的最迟时间 记作vl i 在求解事件vi的最早发生时间ve i 的前提vl n 1 ve n 1 下 从汇点开始 向源点推进得到vl i vl i Min vl k dut S 0 i n 2 其中 S是所有以第i个顶点为弧尾的弧的集合 dut 表示弧对应的活动的持续时间 3 活动ai的最早开始时间e i 如果弧表示活动ai 当事件vk发生之后 活动ai才开始 因此 事件vk的最早发生时间也就是活动ai的最早开始时间 即e i ve k 活动ai的最晚开始时间l i 在不推迟整个工程完成时间的基础上 活动ai最迟必须开始的时间 如果弧表示活动ai 持续时间为dut 则活动ai的最晚开始时间l i vl j dut 5 活动ai的松弛时间 活动ai的最晚开始时间与最早开始时间之差就是活动ai的松弛时间 记作l i e i 利用求AOE网的关键路径的算法 图7 29中的网中顶点对应事件最早发生时间ve 最晚发生时间vl及弧对应活动最早发生时间e 最晚发生时间如图7 30所示 7 4 3最短路径除了连通网的最小生成树之外 我们有时还需要知道两个城市之间是否有通路 在有通路的情况下 走哪条路最短 我们可以用顶点表示城市 带权的弧表示两个城市的距离 这样就把一个实际的问题转化为在带权图中求两个顶点的最短路径问题 1 从某个顶点到其他顶点的最短路径未从有向图顶点v0出发到其余各个顶点的最短路径 带权有向图G7及从v0出发到其他各个顶点的最短路径如图7 31所示 设有一个带权有向图D V E 定义一个数组dist 数组中的每个元素dist i 表示顶点v0到顶点vi的最短路径长度 则长度为dist j Min dist i vi V 的路径表示从顶点v0出发到顶点vj的最短路径 也就是说 在所有的顶点v0到顶点vj的路径中 dist j 是最短的一条路径 而数组dist的初始状态是 如果从顶点v0到顶点vi存在弧 则dist i 是弧的权值 否则 dist j 的值为 迪杰斯特拉算法求解最短路径的步骤如下 假设有向图用邻接矩阵存储 1 初始时 S只包括源点v0 即S v0 V S包括除v0以外的图中的其他顶点 v0到其他顶点的路径初始化为dist i G arc 0 i adj 2 选择距离顶点vi最短的顶点vj 使得dist j Min dist i vi V S dist j 表示从v0到vj最短路径长度 vj表示对应的终点 3 修改从v0到顶点vi的最短路径长度 其中vi S 如果有dist k G arc k i dist i 则修改dist i 使得dist i dist k G arc k i adj 4 重复执行步骤 2 和 3 直到所有从v0到其他顶点的最短路径长度求出 求解最短路径的迪杰斯特拉算法用C语言描述如下 typedefintPathMatrix MAXVERTEX MAXVERTEX 定义一个保存最短路径的二维数组 typedefintShortPathLength MAXVERTEX 定义一个保存从顶点v0到顶点v的最短距离的数组 voidDijkstra MGraphN intv0 PathMatrixpath ShortPathLengthdist 用Dijkstra算法求有向网N的v0顶点到其余各顶点v的最短路径path v 和最短路径长度dist v final v 为1表示v S 即已经求出从v0到v的最短路径 intv w i k min intfinal MAXVERTEX 记录v0到该顶点的最短路径是否已求出 for v 0 v N vexnum v 数组dist存储v0到v的最短距离 初始化为v0到v的弧的距离 final v 0 dist v N arc v0 v adj for w 0 w N vexnum w path v w 0 if dist v INFINITY 如果从v0到v有直接路径 则初始化路径数组 path v v0 1 path v v 1 dist v0 0 v0到v0的路径为0 final v0 1 v0顶点并入集合S 从v0到其余G vexnum 1个顶点的最短路径 并将该顶点并入集合S for i 1 i N vexnum i min INFINITY for w 0 w N vexnum w if final w 利用以上迪杰斯特拉算法求最短路径的思想 图7 30所示图G7的带权邻接矩阵和从顶点v0到其他顶点的最短路径求解过程如图7 31所示 2 任意一对顶点之间的最短路径上述方法只能求出源点到其余顶点的最短路径 如果要计算任意一对顶点间的最短路径 可以用每一顶点作为源点 重复调用迪杰斯特拉算法n次 其时间复杂度为O n3 下面介绍一种形式更简洁的方法 弗洛伊德算法 其时间复杂度也为O n3 算法思想 设图G用邻接矩阵表示 求图G中任意一对顶点vi到vj之间的最短路径 如果从顶点vi到顶点vj存在弧 但是该弧所在的路径不一定是vi到vj的最短路径 需要进行n次比较 首先需要从顶点v0开始 如果有路径 vi v0 vj 存在 则比较路径 vi vj 和 vi v0 vj 选择两者中最短的一个且中间顶点的序号不大于0 然后在路径上再增加一个顶点v1 得到路径 vi v1 和 v1 vj 如果两者都是中间顶点不大于0的最短路径 则将该路径 vi v1 vj 与上面的已经求出的中间顶点序号不大于0的最短路径比较 选中其中最小的作为从vi到vj的中间路径顶点序号不大于1的最短路径 接着在路径上增加顶点v2 得到路径 vi v2 和 v2 vj 按照以上方法进行比较 求出从vi到vj的中间路径顶点序号不大于2的最短路径 依次类推 经过n次比较 可以得到从vi到vj的中间顶点序号不大于n 1的最短路径 依照这种方法 可以得到各个顶点之间的最短路径 根据以上弗洛伊德算法思想 求解任意顶点间的最短路径算法描述如下 voidFloyd MGraphN PathMatrixpath ShortPathLengthdist 用Floyd算法求有向网N的各顶点v和w之间的最短路径 path v w u 表示u是从v到w当前最短路径 intu v w i for v 0 v N vexnum v 初始化数组path和dist for w 0 w N vexnum w dist v w N arc v w adj 初始时 顶点v到顶点w的最短路径为v到w的弧的权值 for u 0 u N vexnum u path v w u 0 路径矩阵初始化为零 if dist v w INFINITY 如果v到w有路径 则由v到w的路径经过v和w两点 path v w v 1 path v w w 1 for u 0 u N vexnum u for v 0 v N vexnum v for w 0 w N vexnum w if dist v u INFINITY 7 5小结 图中顶点间的关系可以是任意的 图是最复杂的非线性结构 图由顶点和边 弧 构成 根据边的有向和无向可以将图分为两种 有向图和无向图 将带权的有向图称为有向网 带权的无向图称为无向网 图的存储结构有四种 邻接矩阵存储结构 邻接表存储结构 十字链表存储结构和邻接多重表存储结构 其中 最常用的是邻接矩阵存储和邻接表存储 图的遍历分为两种 广度优先遍历和深度优先遍历 构造最小生成树的算法主要有两个 普里姆算法和库鲁斯卡尔算法 关键活动决定整个工程完成的日期 非关键活动不能决定工程的进度 最短路径是指从一个顶点到另一个顶点路径长度最小的一条路径 最短路径的算法主要有迪杰斯特拉算法和弗洛伊德算法