【C语言版】7第七章图.ppt

数据结构第七章图计算机科学系施化吉E mail hjshi002 图 Graph 是一种比树更为复杂的非线性数据结构 在树形结构中 数据元素之间的关系是层次型的 树中除叶子以外的每一个数据元素可以和它下一层的多个数据元素存在关系 但除根元素以外的每一个数据元素只能且必须和它上一层中的一个数据元素存在关系 即一对多的关系 而在图形结构中 数据元素之间的关系是任意的 图中每一个数据元素可以和任何其它数据元素相关联 是多对多的关系 本章主要介绍图的存储结构以及图的基本操作的实现 7 1图的基本概念 图是由数据元素的集合及数据元素间的关系集合组成的一种数据结构 Graph V E 其中 V x x 某个数据对象 是数据元素的集合 在图中 数据元素一般被称为顶点 vertex E v w v w V 或E v w VPath v w 表示从顶点v到顶点w的一条单向通路 它是有方向的 7 1 1图的定义 在图中如果顶点对 v w 是无序的 则称此图为无向图 undirectedgraph 顶点对 v w 称为与顶点v和顶点w相关联的一条边 由于这条边没有方向 所以 v w 与 w v 是同一条边 在图中如果顶点对 v w 是有序的 则称此图为有向图 directedgraph 顶点对 v w 称为从顶点v到顶点w的一条有向边 又称为弧 其中v称为有向边 v w 的始点 弧尾 w称为有向边 v w 的终点 弧头 显然 v w 与 w v 是两条不同的弧 一般表示无向图中边的顶点对用一对圆括号括 起来 表示有向图中弧的顶点对用一对尖括号括起来 右图所示的4个图 其中G1和G2是无向图 G3和G4是有向图 在图G3和G4中 为了表示有向边 边的方向用箭头画出 箭头从有向边的始点指向有向边的终点 在无向图中用线段表示边 在下面对图的讨论中 对图作一些限制 第一 图中不能有从顶点自身到自身的边 即自身环 就是说不应有形如 x x 或 x x 的边 如图 a 所示的带自身环的图不讨论 第二 两个顶点v和w之间相关联的边不能多于一条 如图 b 所示的多重图也不讨论 7 1 2图的术语 1 完全图 completegraph 若一个无向图有n个顶点 请问该无向图最多有多少条边 又 若一个有向图有n个顶点 请问该有向图最多有多少条弧 7 1 2图的术语 1 完全图 completegraph 在有n个顶点的无向图中 若有n n 1 2条边 则称此无向图为完全无向图 在有n个顶点的有向图中 若有n n 1 条边 则称此图为完全有向图 显然 在完全图中边 弧 数目达到最大 7 1 2图的术语 2 权 weight 在某些图的应用中 边 弧 上具有与它相关的系数 称之为权 这些权可以表示从一个顶点到另一个顶点的距离 所花费的代价 所需的时间 次数等等 这种带权图也被称为网络 network 分别有 无向网和有向网 无向网 有向网 7 1 2图的术语 3 邻接点 adjacentvertex 如果 v w 是无向图G中的一条边 则称v与w互为邻接顶点 而且边 v w 被称为依附于顶点v和w 如果 v w 是有向图G中的一条弧 则称顶点v邻接到顶点w 也称v是w的前驱 顶点w邻接自顶点v 也称w是v的后继 弧 v w 与顶点v与w相关联 无向网 有向网 4 子图 subgraph 设有两个图G V E 和G V E 若V V且E E 则称图G 是图G的子图 下图 a 和 b 是无向图G1的两个子图 图 c 和 d 是有向图G3的两个子图 7 1 2图的术语 5 顶点的度 degree 无向图中 顶点的度是指与每个顶点相连的边数有向图中 顶点的度分成入度与出度入度ID Vi 是指以该顶点为头的弧的数目出度OD Vi 是指以该顶点为尾的弧的数目顶点的度TD Vi 出度OD Vi 入度ID Vi G2中顶点1的度为2G4中顶点1的入度为2出度为1顶点1的度为3 7 1 2图的术语 6 路径 path 在图G V E 中 若从顶点vi出发 沿一些边 或弧 经过一些顶点vp1 vp2 vpk 到达顶点vj 则顶点序列 vi vp1 vp2 vpk vj 被称为 从顶点vi到顶点vj的路径 路径 1 2 3 5 6 3路径长度 5简单路径 1 2 3 5回路 1 2 3 5 6 3 1简单回路 3 5 6 3 路径 1 2 5 7 6 5 2 3路径长度 7简单路径 1 2 5 7 6回路 1 2 5 7 6 5 2 1简单回路 1 2 3 1 7 1 2图的术语 7 路径长度 pathlength 对于不带权的图 路径长度是指这条路径上边 弧 的数目 7 1 2图的术语 路径 1 2 3 5 6 3路径长度 5简单路径 1 2 3 5回路 1 2 3 5 6 3 1简单回路 3 5 6 3 路径 1 2 5 7 6 5 2 3路径长度 7简单路径 1 2 5 7 6回路 1 2 5 7 6 5 2 1简单回路 1 2 3 1 路径 A B C F路径长度 15 3 2 路径 A E C F B路径长度 9 21 2 7 7 1 2图的术语 7 路径长度 pathlength 对于带权图 路径长度是指路径上各边 弧 的权之和 8 简单路径 回路和简单回路 对于一路径 v1 v2 vm 若路径上各顶点均不相同 则称这路径为简单路径 路径 1 2 3 5 6 3路径长度 5简单路径 1 2 3 5回路 1 2 3 5 6 3 1简单回路 3 5 6 3 路径 1 2 5 7 6 5 2 3路径长度 7简单路径 1 2 5 7 6回路 1 2 5 7 6 5 2 1简单回路 1 2 3 1 7 1 2图的术语 8 简单路径 回路和简单回路 若路径上第一个顶点v1和最后一个顶点vm相同 则称这样的路径为回路或环 7 1 2图的术语 路径 1 2 3 5 6 3路径长度 5简单路径 1 2 3 5回路 1 2 3 5 6 3 1简单回路 3 5 6 3 路径 1 2 5 7 6 5 2 3路径长度 7简单路径 1 2 5 7 6回路 1 2 5 7 6 5 2 1简单回路 1 2 3 1 8 简单路径 回路和简单回路 若回路中除起点和终点相同外 其余顶点各不相同 则称为简单回路 7 1 2图的术语 路径 1 2 3 5 6 3路径长度 5简单路径 1 2 3 5回路 1 2 3 5 6 3 1简单回路 3 5 6 3 路径 1 2 5 7 6 5 2 3路径长度 7简单路径 1 2 5 7 6回路 1 2 5 7 6 5 2 1简单回路 1 2 3 1 9 连通图与连通分量 在无向图中 若从顶点vi到顶点vj有路径 则称顶点vi与vj是连通的 如果无向图中任意两个顶点都是连通的 则称此无向图是连通图 非连通图的极大连通子图 包括所有连通的顶点和这些顶点依附的所有的边 叫做连通分量 如右图 a 所示是一个非连通图 图 b 所示是相应的三个连通分量 7 1 2图的术语 G是一个共有28条边的非连通无向图 则该图至少有个顶点 9 10 强连通图与强连通分量 stronglyconnecteddigraph 在有向图中 若对于顶点vi和vj 同时存在一条从vi到vj和从vj到vi的路径 则称顶点vi和顶点vj是强连通的 如果有向图中任意两个顶点都是强连通的 则称此有向图为强连通图 非强连通图的极大强连通子图叫做强连通分量 G3是强连通图 G4是非强连通图 G4有两个强连通分量 7 1 2图的术语 11 生成树和生成森林 对非连通图 则称由各个连通分量的生成树的集合为此非连通图的生成森林 假设一个连通图有n个顶点和e条边 其中n 1条边和n个顶点构成一个极小连通子图 称该极小连通子图为此连通图的生成树 7 1 2图的术语 11 生成树和生成森林 如果一个有向图只有一个入度为零的顶点 且其它顶点的入度均为1 则称这个有向图为有向树 一个有向图的生成森林 是由若干棵互不相交的有向树组成 含有图中全部顶点和图中的部分弧 7 1 2图的术语 7 1 3图的抽象数据类型定义 图是一种数据结构 加上一组基本操作就构成了图的抽象数据类型 图的抽象数据类型定义如下 ADTGraph 数据对象V 具有相同特性的数据元素的集合 称为顶点集 数据关系R R VR VR v w V p v w 表示从v到w的弧 P v w 定义了弧的信息 基本操作P Create Graph 图的创建操作 初始条件 无 操作结果 生成一个没有顶点的空图G GetVex G v 求图中的顶点v的值 初始条件 图G存在 v是图中的一个顶点 操作结果 生成一个没有顶点的空图G DFStraver G V 从v出发对图G深度优先遍历 初始条件 图G存在 操作结果 对图G深度优先遍历 每个顶点访问且只访问一次 BFStraver G V 从v出发对图G广度优先遍历 初始条件 图G存在 操作结果 对图G广度优先遍历 每个顶点访问且只访问一次 ADTGraph详见p156 157 由于在图中 任何两个顶点之间都可能存在联系 所以无法在存储位置上反映数据元素之间的联系 因此图没有顺序存贮结构 按图中顶点之间的联系 图的存储结构似乎采用多重链表表示比较恰当 但是若采用多重链表 则链表中结点的结构难以确定 7 2图的存储结构 但是若采用多重链表 则链表中结点的结构难以确定 因为结点中的指针数若按顶点度的最大值来设置 则会浪费空间 因为有很多顶点的度小于最大值 7 2图的存储结构 若顶点的指针数按每个顶点的度数来设置 则存储结构中会有很多顶点的结构不一致 给图的运算带来困难 7 2图的存储结构 因此 图的存储结构不宜采用多重链表 图的存贮结构应根据具体问题的要求来设计 常用的存贮结构有邻接矩阵 邻接表 邻接多重表和十字链表 7 2图的存储结构 7 2 1邻接矩阵 在图的邻接矩阵表示中 除了记录每一个顶点信息的顶点表外 还有一个表示各个顶点之间关系的矩阵 称之为邻接矩阵 若设图G V E 是一个有n个顶点的图 则图的邻接矩阵是一个二维数组arcs n n 它的定义为 对于网络 或带权图 邻接矩阵定义如下 下图给出了无向图 有向图和有向网的邻接矩阵 其中 一维数组vertexes 用于存储顶点的信息 二维数组arcs 用于存储边 或弧 的信息 7 2 1邻接矩阵 从图中可知 无向图的邻接矩阵是对称的 将第i行的元素值或第i列的元素值累加起来就得到顶点i的度 即 7 2 1邻接矩阵 有向图的邻接矩阵可能不对称 如果第i行第j列为1 则表示有一条从顶点Vi到顶点Vj的有向边 将第i行的所有元素值累加起来就得到顶点Vi的出度OD Vi 如果第j行第i列为1 则表示有一条从顶点Vj到顶点Vi的有向边 将第i列的所有元素值累加起来就得到顶点Vi的入度ID Vi 7 2 1邻接矩阵 7 2 2邻接表 实现 为图中每个顶点建立一个单链表 第i个单链表中的结点表示依附于顶点Vi的边 有向图中指以Vi为尾的弧 顶点结点 data域 存放顶点信息firstarc域 指示第一个邻接点 弧 边 结点 adjvex域 邻接点域 存放与Vi邻接的点在顶点数组中的位置nextarc域 指示下一条边或弧 下一个邻接点 下图 b 所示的是有向图的邻接表表示 7 2 2邻接表 有向图中顶点Vi的出度为第i个单链表中的弧结点个数顶点Vi的入度为所有单链表中邻接点域值是i的弧结点个数 特点无向图中顶点Vi的度为第i个单链表中的边结点数 计算顶点的入度比较麻烦 7 2 2邻接表 为此 对有向图可以建立逆邻接表 如图 c 所示 在有向图的逆邻接表中 顶点vi的弧链表中链接的是所有以vi为弧头的弧尾顶点 7 2 2邻接表 对于带权图 网络 必须在邻接表的边 或弧 结点中增加一个存放边 或弧 上的权值的域weight 如下图所示的是一个带权图的邻接表表示 7 2 2邻接表 在邻接表的边 或弧 链表中 各个边 或弧 结点的链入顺序任意 视边 或弧 结点输入次序而定 设图中有n个顶点 e条边 则用邻接表表示无向图时 需要n个顶点结点 2e个边结点 用邻接表表示有向图时 若不考虑逆邻接表 只需n个顶点结点 e个弧结点 7 2 2邻接表 图的邻接表结构描述 7 2 2邻接表 链表结点 边结点 typedefstructnode intadjvex 邻接点域 存放与Vi邻接的点在表头数组中的位置structnode next 链域 指示下一条边或弧 EdgeNode 表头结点 typedefstructVnode datatypevexdata 存放顶点信息EdgeNode firstarc 指示第一个邻接点 VNode 图的邻接表 typedefVNodeAdjListType MaxVertexNum AdjList是邻接表类型 邻接表建立算法 存储结构定义typedefstruct AdjListTypeadjlist 邻接表 intn e 顶点数和边数 ALGraph ALGraph是以邻接表方式存储的图类型 算法流程 有向图为例 1 读入顶点数和边数 2 读入顶点信息 据此创建表头数组 3 读入弧信息 即代表弧头和弧尾的序号 i j 据此创建结点的邻接表 a 新一个生成链表结点 b 新生成的结点插入到第i条链表中 voidCreateALGraph ALGraph G 建立有向图的邻接表存储 inti j k EdgeNode s printf 输入顶点数和边数 输入格式为 顶点数 边数 n scanf d d CreateALGraph voidCreateALGraph ALGraph G 建立有向图的邻接表存储 inti j k EdgeNode s printf 输入顶点数和边数 输入格式为 顶点数 边数 n scanf d d CreateALGraph voidCreateALGraph ALGraph G 建立有向图的邻接表存储 inti j k EdgeNode s 建立有n个顶点的顶点表 以下 输入每一条弧的信息 并生成弧结点 建立弧结点链表 printf 请输入边的信息 输入格式为 i j n for k 0 ke k 建立边表 scanf n d d CreateALGraph 7 2 3十字链表 引入十字链表的原因 1 对已经处理过的弧作标记在邻接表 或逆邻接表 表示时不方便2 要同时做到计算出 入度也不方便 邻接表只对出度计算方便 逆邻接表只对入度计算方便 为此 引入新的结构 十字链表结构 十字链表主要针对有向图 7 2 4十字链表 在有向图的十字链表中 图中的每一条弧用一个弧结点表示 弧结点的结构如图 尾域tailvex 指示弧尾顶点在图中的位置 头域headvex 指示弧头顶点在图中的位置 7 2 4十字链表 在有向图的十字链表中 图中的每一条弧用一个弧结点表示 弧结点的结构如图 指针域hlink 指向弧头相同的下一条弧 指针域tlink 指向弧尾相同的下一条弧 info域 指向该弧的相关信息 7 2 4十字链表 对有向图中的每一个顶点也用一个顶点结点表示 它由三个域组成 顶点结点的结构如图 data域 存储和顶点相关的信息 指针域firstin 指向以该顶点为弧头的第一条弧所对应的弧结点 指针域firstout 指向以该顶点为弧尾的第一条弧所对应的弧结点 在有向图的十字链表中 从顶点结点中的firstout域出发 由弧结点中的tlink域链接起来的链表 正好是原来的邻接表结构 统计该链表中弧结点的个数 可求得该顶点的出度 7 2 4十字链表 在有向图的十字链表中 从顶点结点中的firstin域出发 由弧结点中的hlink域链接起来的链表 正好是原来的逆邻接表结构 统计该链表中弧结点的个数 可求得该顶点的入度 7 2 4十字链表 结点类型定义 defineINFINITYMAX VAL 最大值 defineMAX VEX30 最大顶点数typedefstructArcNode inttailvex headvex 尾结点和头结点在图中的位置InfoTypeinfo 与弧相关的信息 如权值structArcNode hlink tlink ArcNode 弧结点类型定义 typedefstructVexNode VexTypedata 顶点信息ArcNode firstin firstout VexNode 顶点结点类型定义 typedefstruct intvexnum VexNodexlist MAX VEX OLGraph 图的类型定义 typedefstruct intvexnum arcnum 当前顶点数和弧数VexNodexlist MAX VEX 顶点 表头数组 OLGraph 图的类型定义 7 2 3邻接多重表 引入邻接多重表结构的原因 在一些较复杂的问题中 有时需要给被访问过的边加以标记 若用邻接表 则需要对一条边的两个边结点同时作标记 但是这两个顶点不在同一条边结点链表中 很不方便 为此 引入新的结构 邻接多重表结构 邻接多重表主要针对无向图 7 2 4邻接多重表 邻接多重表的结构和十字链表类似 每条边用一个结点表示 邻接多重表中的顶点结点结构与邻接表中的完全相同 而表结点包括六个域如图所示 Data域 存储和顶点相关的信息 指针域firstedge 指向依附于该顶点的第一条边所对应的表结点 标志域mark 用以标识该条边是否被访问过 7 2 4邻接多重表 邻接多重表的结构和十字链表类似 每条边用一个结点表示 邻接多重表中的顶点结点结构与邻接表中的完全相同 而表结点包括六个域如图所示 ivex和jvex域 分别保存该边所依附的两个顶点在图中的位置 info域 保存该边的相关信息 指针域ilink 指向下一条依附于顶点ivex的边 指针域jlink 指向下一条依附于顶点jvex的边 邻接多重表与邻接表的区别 邻接表的同一条边用两个表结点表示 而邻接多重表只用一个表结点表示 除标志域外 邻接多重表与邻接表表达的信息是相同的 因此 操作的实现也基本相似 结点类型定义 defineINFINITYMAX VAL 最大值 defineMAX VEX30 最大顶点数 typedefemnu unvisited visited Visitting typedefstructEdgeNode Visittingmark 访问标记intivex jvex 该边依附的两个结点在图中的位置InfoTypeinfo 与边相关的信息 如权值structEdgeNode ilink jlink 分别指向依附于这两个顶点的下一条边 EdgeNode 弧边结点 表结点 类型定义 typedefstructVexNode VexTypedata 顶点信息ArcNode firsedge 指向依附于该顶点的第一条边 VexNode 顶点结点类型定义 typedefstruct intvexnum VexNodemullist MAX VEX AMGraph 7 3图的遍历与连通性 对于给定的图 沿着一些边 或弧 访问图中所有的顶点 且使每个顶点仅被访问一次 这个过程叫做图的遍历 图的遍历通常有两种方法 深度优先遍历 DepthFirstTraversal 和广度优先遍历 BreadthFirstTraversal 这两种方法对无向图和有向图都是适用的 但在下面的讨论中将主要介绍对无向图的遍历 图的遍历操作更复杂表现在 在图结构中 没有一个 自然 的首结点 图中任意一个顶点都可作为第一个被访问的结点 在非连通图中 从一个顶点出发 只能够访问它所在的连通分量上的所有顶点 因此 还需考虑如何选取下一个出发点以访问图中其余的连通分量 在图结构中 如果有回路存在 那么一个顶点被访问之后 有可能沿回路又回到该顶点 在图结构中 一个顶点可以和其它多个顶点相连 当这样的顶点访问过后 存在如何选取下一个要访问的顶点的问题 7 3 1深度优先遍历 图的深度优先遍历基于深度优先搜索DFS DepthFirstSearch 深度优先搜索 DFS 方法 从图的顶点V0出发 先访问顶点V0 再访问V0的一个未被访问过的邻接顶点V1 再从V1出发访问V1的某个未被访问过的邻接顶点 直到一个其所有的邻接顶点都已被访问过的顶点 接着退回到尚有邻接顶点未被访问过的顶点 再从该顶点出发 重复上述过程 显然是一个递归的过程 直到所有的被访问过的顶点的邻接顶点都被访问过为止 这是一个递归定义 所以图的深度优先搜索可以用递归算法实现 下图 a 给出了深度优先搜索的示例 由于该图是连通的 所以从顶点A出发 通过一次深度优先搜索 就可以访问图中的所有顶点 从图的顶点V0出发 先访问顶点V0 再访问V0的一个未被访问过的邻接顶点V1 再从V1出发访问V1的某个未被访问过的邻接顶点 直到一个其所有的邻接顶点都已被访问过的顶点 接着退回到尚有邻接顶点未被访问过的顶点 再从该顶点出发 重复上述过程 显然是一个递归的过程 直到所有的被访问过的顶点的邻接顶点都被访问过为止 7 3 1深度优先遍历 图的深度优先遍历的访问顺序与树的前序遍历顺序类似 图 b 给出了在深度优先遍历的过程中 访问的所有顶点和经过的边 图中各顶点旁附加的数字表示各顶点被访问的次序 在图 b 中 共有n 1条边连结了所有n个顶点 在此把它称为图 a 的深度优先搜索生成树 DFS生成树 7 3 1深度优先遍历 深度遍历 V1 V2 V4 V8 V5 V6 V3 V7 深度遍历 V1 V3 V6 V8 V7 V5 V2 V4 7 3 1深度优先遍历 从指定的结点v开始进行深度优先搜索 DFS 的算法的步骤是 1 访问结点v 并标记v已被访问 2 取顶点v的第一个邻接顶点w 3 若顶点w不存在 算法结束 否则继续步骤 4 4 若顶点w未被访问 则从w开始进行深度优先搜索 DFS 然后转步骤 5 否则 直接转步骤 5 5 令w为顶点v的在原来w之后的下一个邻接顶点 转到步骤 3 7 3 1深度优先遍历 深度优先遍历算法流程 为了实现图的深度和广度遍历算法 我们要引入一个辅助数组visited 其作用是用来标志某个顶点是否已经被访问过 7 3 1深度优先遍历 typedefemnu FALSE TRUE BOOLEAN BOOLEANVisited MAX VEX voidDFS ALGraph G intv 深度优先搜索一个连通图LinkNode p Visited v TRUE Visit v 置访问标志 访问顶点v p G AdjList v firstarc 取第一个邻接点 while p NULL 有邻接点 if Visited p adjvex DFS G p adjvex 从v的未访问过的邻接顶点出发深度优先搜索 p p nextarc 求下一个邻接点 7 3 1深度优先遍历 深度遍历 V1 V3 V7 V6 V2 V5 V8 V4 7 3 1深度优先遍历 深度遍历 V1 V3 V7 V6 V2 V4 V8 V5 7 3 1深度优先遍历 7 3 1深度优先遍历 例 已知带权有向图的邻接表如下图所示 要求 1 画出该带权有向图 2 求出基于该邻接表的从顶点A出发的深度优先搜索的顶点序列以及DFS生成树 voidDFS traverse Grapg ALGraph G intv for v 0 vvexnum v Visited v FALSE 访问标志初始化 for v 0 vvexnum v if Visited v DFS G v 深度优先遍历任意图 7 3 1深度优先遍历 7 3 2广度优先遍历 图的广度优先遍历基于广度优先搜索BFS BreadthFirstSearch 广度优先搜索是从图中某一顶点v出发 在访问顶点v后再访问v的各个未被访问过的邻接顶点w1 w2 wk 然后再依次访问w1 w2 wk的所有还未被访问过的邻接顶点 继续从这些访问过的顶点出发 再访问它们的所有还未被访问过的邻接顶点 如此下去 直到图中所有和顶点v由路径连通的顶点都被访问到为止 下图 a 给出了一个从顶点A出发进行广度优先遍历的示例 图 b 给出了由广度优先遍历得到的广度优先生成树 BFS生成树 它由遍历时访问过的n个顶点和遍历时经历的n 1条边组成 各顶点旁边附的数字标明了顶点被访问的顺序 广度优先搜索是从图中某一顶点v出发 在访问顶点v后再访问v的各个未被访问过的邻接顶点w1 w2 wk 然后再依次访问w1 w2 wk的所有还未被访问过的邻接顶点 继续从这些访问过的顶点出发 再访问它们的所有还未被访问过的邻接顶点 如此下去 直到图中所有和顶点v由路径连通的顶点都被访问到为止 7 3 2广度优先遍历 从指定的结点v开始进行广度优先搜索的算法步骤是 1 访问结点v 并标记v已被访问 同时顶点v入队列 2 当队列空时算法结束 否则继续步骤 3 3 队头顶点出队列为v 4 取顶点v的第一个邻接顶点w 5 若顶点w不存在 转步骤 2 继续出队 否则继续步骤 6 6 若顶点w未被访问 则访问结点w 并标记w已被访问 同时顶点w入队列 然后转步骤 7 否则直接转步骤 7 7 令w为顶点v的在原来w之后的下一个邻接顶点 转到步骤 5 7 3 2广度优先遍历 7 3 2广度优先遍历 广度优先遍历任意图 VoidBFSTraverse ALGraphg intn for i 1 i n i visited i 0 0表示未被访问i 1 while i n if visited i BFS g i visited 广度优先 遍历图g中结点i的所 有未访问的邻接点i 7 3 2广度优先遍历 typedefstructnode intadjvex structnode next EdgeNode 边 弧 结点 广度优先搜索BFS 以邻接表为例 邻接表存储结构描述如下 typedefstructVnode intvexdata structEdgeNode firstarc VNode 顶点结点 typedefVNodeAdjList MaxVertexNum typedefstruct 邻接表作为图的存储结构AdjListadjlist 邻接表类型intn e ALGraph 是否已经被访问的辅助数组 typedefemnu FALSE TRUE BOOLEAN BOOLEANVisited MAX VEX 7 3 2广度优先遍历 VoidBFS ALGraphg intv intvisited 基于邻接表存储的图类型 利用一维数组实现队列的存储 f r为队首和队尾指针 且都指向实际的队首和队尾元素 intqu MaxVertexNum f r f 0 r 0 队列的初始化printf d v visited v 1 qu 0 v 结点序号v入队while fadjvex 求该邻接点在访问标志数组中的下标if visited j 0 判断该邻接点有没访问过 visited j 1 printf d n j qu r j w w next 7 3 2广度优先遍历 7 3 2广度优先遍历 7 3 2广度优先遍历 7 3 2广度优先遍历 以上都是以无向图为例 实际上DFS和BFS对有向图也是适用的 7 3 2广度优先遍历 7 3 2广度优先遍历 7 3 3连通分量 对于连通图 从任一顶点出发 只需一次调用深度优先搜索算法或广度优先搜索算法就可以访问到图中的所有顶点 对于非连通图时 从图中某一顶点出发 一次调用深度优先搜索算法或广度优先搜索算法不可能访问到图中的所有顶点 只能访问到该顶点所在的极大连通子图 即连通分量 的所有顶点 非连通图有n个连通分量 就要n次调用DFS或BFS才能访问图中的所有顶点 若从图的每一个连通分量中的一个顶点出发进行搜索 就可以求得图的所有连通分量 所谓连通分量是指非连通图中极大连通子图 7 4最小生成树 一个连通图的生成树是原图的极小连通子图 它包含原图中的所有n个顶点和使n个顶点连通的n 1条边 这意味着对于生成树来说 若删除它的一条边 就会使生成树变成非连通图 若给它增加一条边 就会形成图中的一个回路 另一方面 一个连通图的生成树不是唯一的 使用不同的方法遍历图 可以得到不同的生成树 从不同的顶点出发 也可能得到不同的生成树 而且生成树有时还和图的存储结构中具体的结点顺序有关 比如邻接表中各结点的次序 对于一个有n个顶点的带权的连通图 即网络 可以有不同的生成树 每一棵生成树都可以构成通信网络 我们希望能够根据各条边上的权值 选择一棵总造价最小的生成树 这就是构造网络的最小 代价 生成树 Minimum costSpanningTree 问题 如何找这样的最小生成树 常用的构造网络的最小 代价 生成树算法有 普里姆 Prim 算法和克鲁斯卡尔 Kruskal 算法 7 4最小生成树 7 4 1普里姆算法 普里姆 Prim 算法的基本思想是 假设连通网络为N V E TE为N的最小生成树上边的集合 开始时TE U为算法在构造最小生成树过程中已得到的顶点集 开始时U u0 u0 V 算法从N中的某一顶点u0出发 选择与u0关联的具有最小权值的边 vi u0 将顶点vi加入到生成树的顶点集合U中 vi u0 加入到集合TE中 以后每一步从一个顶点在V U中 而另一个顶点在U中的各条边当中选择权值最小的边 v u v V U u U 把顶点v加入到集合U中 边 v u 加入到集合TE中 如此重复 直到网络中的所有顶点都加入到生成树顶点集合U U V 中为止 此时 TE中刚好有n 1条边 则T V TE 为连通网络N的最小生成树 如果对上述算法思想按步骤来描述 则可以描述如下 普里姆 Prim 算法思想设G V E 是连通网 TE是G上最小生成树中边的集合 1 初始时 令U u0 u0 V TE 2 在所有v V U u U的边 v u E中 找一条代价最小的边 v0 u0 3 将 v0 u0 并入集合TE 同时v0并入U 即TE TE v0 u0 U U v0 4 重复上述 2 3 操作直至U V为止 则T V TE 为G的最小生成树 7 4 1普里姆算法 对于图 a 所示的连通网络 下图 a f 给出了按普里姆算法从顶点A开始构造最小生成树的过程 7 4 1普里姆算法 1 7 4 1普里姆算法 算法实现说明设用邻接矩阵 二维数组 表示图 两个顶点之间若不存在边 则其权值为机内允许的最大值 在利用普里姆算法构造最小生成树过程中 需要设置了一个辅助数组closearc 以记录从V U中顶点到U中顶点具有最小权值的边 从A出发时的情况如图 算法实现说明 在利用普里姆算法构造最小生成树过程中 需要设置了一个辅助数组closearc 以记录从V U中顶点到U中顶点具有最小权值的边 对每一个顶点v V U 在辅助数组中有一个分量closearc v 它包括两个域 lowweight和nearvertex 其中 lowweight中存放顶点v到U中的各顶点的边上的当前最小权值 lowweight 0表示v U nearvertex记录顶点v到U中具有最小权值的那条边的另一个邻接顶点u nearvertex 1表示该顶点v为开始顶点 假设普里姆算法从顶点A 设顶点A的序号为0 出发 即u0 0 则初始closearc数组如图所示 算法实现说明 算法思想 从closearc 中选择一条权值 不为0 最小的边 vk vj 然后做 置closearc k lowweight为0 表示vk已加入到U中 根据新加入的vk更新closearc 中每个元素 vi V U 若cost i k colsearc i lowweight 表明在U中新加入顶点vk后 vi vk 成为vi到U中权值最小的边 置 重复 n 1次就得到最小生成树 普里姆算法具体步骤见下页 普里姆算法具体步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 共n 1次 n是图的顶点数 lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 n 1次 3 在closearc 中选择lowweight 0 lowweight最小的顶点v 即选中的权值最小的边为 closearc v nearvertex v lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 n 1次 3 在closearc 中选择lowweight 0 lowweight最小的顶点v 即选中的权值最小的边为 closearc v nearvertex v 4 将closearc v lowweight改为0 表示顶点v已加入顶点集U中 并将边 closearc v nearvertex v 加入生成树T的边集合 lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 n 1次 3 在closearc 中选择lowweight 0 lowweight最小的顶点v 即选中的权值最小的边为 closearc v nearvertex v 4 将closearc v lowweight改为0 表示顶点v已加入顶点集U中 并将边 closearc v nearvertex v 加入生成树T的边集合 5 对V U中的每一个顶点j lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 5 对V U中的每一个顶点j 如果依附于 顶点j 和刚加入U集合的 新顶点v 的边的权值Arcs v j 是小于原来依附于j和生成树顶点集合中顶点的边的最短距离closearc j lowweight 此时 新顶点v是F 那么就修改closearc j 使其lowweight Arcs v j nearvertex v 此时j是B C D E这些顶点B 不变 C 由46改为25 D 由 改为25 E 由 改为26C D E的nearvertex也都改为F的编号5 lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 n 1次 3 在closearc 中选择lowweight 0 lowweight最小的顶点v 即选中的权值最小的边为 closearc v nearvertex v 4 将closearc v lowweight改为0 表示顶点v已加入顶点集U中 并将边 closearc v nearvertex v 加入生成树T的边集合 5 对V U中的每一个顶点j 如果依附于 顶点j 和刚加入U集合的 新顶点v 的边的权值Arcs v j 是小于原来依附于j和生成树顶点集合中顶点的边的最短距离closearc j lowweight 那么就修改closearc j 使其lowweight Arcs v j nearvertex v lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 1 初始化辅助数组closearc 2 重复下列步骤 3 4 和 5 n 1次 3 在closearc 中选择lowweight 0 lowweight最小的顶点v 即选中的权值最小的边为 closearc v nearvertex v 此时选中的是v 2 顶点C 4 将closearc v lowweight改为0 表示顶点v已加入顶点集U中 并将边 closearc v nearvertex v 加入生成树T的边集合 lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 普里姆算法步骤如下 5 对V U中的每一个顶点j 如果依附于 顶点j 和刚加入U集合的 新顶点v 的边的权值Arcs v j 是小于原来依附于j和生成树顶点集合中顶点的边的最短距离closearc j lowweight 此时 新顶点v是C 那么就修改closearc j 使其lowweight Arcs v j nearvertex v 此时j是B D E这些顶点B 不变 E不变 D 由25改为17D的nearvertex改为C的编号2 lowweight 0表示v U nearvertex 1表示该顶点v为开始顶点 下图给出了对于前图 a 所示的连通网络 按普里姆算法构造最小生成树时辅助数组closearc 的变化过程 初始时 令U A 即令closearc 0 lowweight 0 并在所有值不为0的lowweight中找最小的lowweight 19 此时为 F A 将F并入U 即令closearc 5 lowweight 0 并修改所有的lowweight不为0的各点的lowweight和nearver 然后再找最小的lowweight 25 此时为 C F 将C并入U 即令closearc 2 lowweight 0 并修改所有的lowweight不为0的各点的lowweight和nearver 然后再找最小的lowweight 17 此时为 D C 将E并入U 即令closearc 4 lowweight 0 并修改所有的lowweight不为0的各点的lowweight和nearver 然后再找最小的lowweight 12 此时为 B E 将B并入U 即令closearc 1 lowweight 0 接下来再也找不到lowweight不为0的顶点了 说明U中已经包含所有顶点 即U V了 结束 将D并入U 即令closearc 3 lowweight 0 并修改所有的lowweight不为0的各点的lowweight和nearver 此时B E都不改变 然后再找最小的lowweight 26 此时为 E F 算法实现 图用邻接矩阵表示 voidMiniSpanTree Prim MgraphG VertexTypeu struct VertexTypenearver 顶点信息VRTypelowweight 权值信息 closearce Max Vertex num ui LocateVex G u 假设ui为0 closearc 0 nearver 1 从序号为0的顶点生成最小生成树closearc 0 lowweight 0 将该顶点加入U集for i 1 i n i 初始化closearcclosearc i nearver 0 closearc i lowweight G arcs 0 i adj adj是权值 借助一结构体数组来存放从U到V U上具有最小权值的边 for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim 初始 mincost j 1 k 1 j 1 n 6 34 mincost mincost 34 k j 1 j 2 n 6 46 mincost 34 mincost 34 k 1不变 j 3 n 6 mincost 34 mincost 34 k 1不变 j 4 n 6 mincost 34 mincost 34 k 1不变 j 5 n 6 19 mincost 34 mincost 19 k j 5 j 6 n 6 退出循环 for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost k位置上所表示的顶点并入U集 重复n 1次 MiniSpanTree Prim for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim 最后再回顾一下整个算法 算法实现 图用邻接矩阵表示 voidMiniSpanTree Prim MgraphG VertexTypeu struct VertexTypenearver 顶点信息VRTypelowweight 权值信息 closearce Max Vertex num ui LocateVex G u 假设ui为0 closearc 0 nearver 1 从序号为0的顶点生成最小生成树closearc 0 lowweight 0 将该顶点加入U集for i 1 i n i 初始化closearcclosearc i nearver 0 closearc i lowweight G arcs 0 i adj adj是权值 借助一结构体数组来存放从U到V U上具有最小权值的边 for i 1 i n i 重复n 1次mincost MAXCOST MAXCOST为一个极大的常量值 j 1 k 1 j为计数器变量 k为辅助数组中权值最小的下标位置while j n 寻找当前最小权值的边的顶点 if closearc j lowcost mincost 重复n 1次 MiniSpanTree Prim 算法分析 设带权连通图有n个顶点 则算法的主要执行是二重循环 求closearc中权值最小的边 频度为n 1 修改closearc数组 频度为n 因此 整个算法