数据结构-第7章图

1、ADT Graph 数据对象数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R：RVRVR| v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 第七章第七章 图图7.1 图的定义和术语图的定义和术语有向图、 无向图、 网、 子图 弧头、 弧尾、 边完全图、 稀疏图、 稠密图 邻接点、 度、 入度、 出度路径、 路径长度、 回路简单路径、 简单回路连通图、 连通分量、强连通图、 强连通分量生成树、 生成森林、 最小生成树名词和术语名词和术语结构的建立和销毁:CreateGraph(&G,V,VR); / 按V和VR的定义构造图G。Destr

2、oyGraph(&G); / 销毁图G。对顶点的访问操作:LocateVex(G, u); / 若G中存在顶点u，则返回该顶点/ 在图中位置位置；否则返回其它信息。GetVex(G, v); / 返回v的值。PutVex(&G, v, value); / 对v赋值value。图的基本操作图的基本操作FirstAdjVex(G, v); / 返回v的第一个邻接点。若该顶点/在G中没有邻接点，则返回“空”。NextAdjVex(G, v, w); /返回v的（相对于w的）下一个/ 邻接点。若w是v的最后一个邻/ 接点，则返回“空”。插入或删除顶点InsertVex(&G, v); / 在图G中增添

3、新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。对邻接点的操作对邻接点的操作:插入和删除弧插入和删除弧InsertArc(&G, v, w); / 在G中增添弧，若G是无/ 向的，则还增添对称弧。DeleteArc(&G, v, w); /在G中删除弧，若G是无/ 向的，则还删除对称弧。遍历遍历DFSTraverse(G, v, Visit(); / 从顶点v起深度优先遍历图/ G，并对每个顶点调用函数/ Visit一次且仅一次。BFSTraverse(G, v, Visit(); / 从顶点v起广度优先遍历图/ G，并对每个顶点调用函数/ Visit一次且仅一次

4、。图的邻接矩阵7.2 图的存储表示图的存储表示图的邻接矩阵 1 边或弧 aIj= 0 无网的邻接矩阵定义 wi,j 边或弧 aIj= 0， 无一般用二维数组表示类型描述：类型描述：#define M_V_NUM 20typedef struct ArcCell VertexType adj; InfoType *info ArcCell, AdjListM_V_NUMM_V_NUM;typedef struct vertextype vexm_v_num AdjList arc; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 mgrap

5、h;有关运算见有关运算见P1622 邻接表adjvexnextarcinfodatafirstarc表结点 头结点#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; /表结点typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM; /头结点typedef struct AdjList vertices;int ve

6、xnum, arcnum; int kind; ALGraph; 类似的有逆邻接表类似的有逆邻接表3。十字链表。十字链表 tailvexheadvexhlinktlinkinfo 顶点结点datafirstinfirstout弧结点有向图的邻接表和逆邻接表的结合 #define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex; / 该弧的尾和头顶点的位置struct ArcBox *hlink, *tlink; InfoType *info; / 该弧相关信息的指针 ArcBox;typedef struct VexNod

7、e VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph;例：如图7.11所示。P165类型描述类型描述4。邻接多重表。邻接多重表 边结点顶点结点markivexilinkjvexjlinkinfo data firstedge #define MAX_VERTEX_NUM 20typedef emnu unvisited, visited VisitIf;t

8、ypedef struct Ebox VisitIf mark; / 访问标记int ivex, jvex; / 该边依附的两个顶点的位置struct EBox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边InfoType *info; / 该边信息指针 EBox;typedef struct VexBox VertexType data;EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;typedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum, edgenum; / 无向图的当前顶点数

9、和边数 AMLGraph; 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。一、深度优先搜索一、深度优先搜索从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。7.3 图的遍历图的遍历/- 下列算法使用的全局变量 -Boolean visitedMAX; / 访问标志数组Status (* VisitFunc)(int v); / 函数变量voidGrap

10、h G, Status (*Visit)(int v) / 对图G作深度优先遍历。VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFSvoid DFS(Graph G, int v) / 从第v个顶点出发递归地深度优先遍历图G。visitedv = TRUE; VisitFunc(v); / 访问第v个顶点for ( w=FirstAdjVex(G, v); w!=0;

11、w=NextAdjVex(G, v, w) )if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w递归调用DFS计算时间O（n+e）深度优先遍历深度优先遍历从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。二、广度优先搜索二、广度优先搜索void BFSTraverse(Graph G, Status (*Visit)(in

12、t v) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。for (v=0; vG.vexnum; +v) visitedv = FALSE;InitQueue(Q); / 置空的辅助队列Qfor ( v=0; vG.vexnum; +v )if ( !visitedv) / v尚未访问EnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为uvisitedu = TRUE; Visit(u); / 访问ufor ( w=FirstAdjVex(G, u); w!=0; w=NextAd

13、jVex(G, u, w) )if ( ! visitedw) EnQueue(Q, w); / u的尚未访问的邻接顶点w入队列Q7.4 图的连通性问题图的连通性问题1.无向图的连通分量和生成树无向图的连通分量和生成树连通图从一个结点出发，可访问图中所有顶点，对于非连通图，则需从多个顶点出发，才能访问所有顶点。每一个出发点，遍历时，所访问的点为其分量的顶点。求连通过分量求连通过分量，则只需将对应的边全部加入到分量顶点中即可。算法7。7 深度优先生成森林。P171*2.有向图的强连通分量有向图的强连通分量深度优先搜索是求有向图的强连通分量的一个新的有效方法。十字链表存贮由某顶点出发，作逆向深度深

14、度优先搜索的顶点集是有向图G中的个强连通的顶点集。问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。3 最小生成树最小生成树算法一：（普里姆算法）算法一：（普里姆算法）可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上

15、的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。记录从顶点集U到VU的代价最小的边的辅助数组：struct VertexType adjvex;VRType lowcost; closedgeMAX_VERTEX_NUM;k = LocateVex ( G, u ); / 顶点u为构造生成树的起始点for ( j=0; jG.vexnum; +j ) / 辅助数组初始化if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uufor (i=0; iG.vexnum; +i) /在其余顶点中选择

16、k = minimum(closedge); / 求出T的下一个结点(k)printf(closedgek.adjvex, G.vexsk); / 输出生成树的边closedgek.lowcost = 0; / 第k顶点并入U集for (j=0; jG.vexnum; +j)if (G.arcskj.adj closedgej.lowcost)closedgej = G.vexsk, G.arcskj.adj ;/ 新顶点并入U后重新选择最小边算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构

17、造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。算法算法:构造非连通图 ST=( V, );k = i = 0;while (kadjvex;DFSArticul(G, v); / 从第v顶点出发深度优先搜索if (count nextarc) w = p-adjvex; / w为v0的邻接顶点if (visitedw = 0) / w未曾被访问DFSArticul(G, w); / 返回前求得lowwif (loww =visitedv0) printf(v0, G.verticesv0.data);

18、 / 输出关节点elseif (visitedw min) min = visitedw; / w是回边上的顶点lowv0 = min; 7.5 有向无环图及其应用有向无环图及其应用一个无环的有向图，称有向无环图称有向无环图。DAG图图7.21 P179有向无环图的应用：（1） 描述表达式描述表达式图7.23 P179（2）描述工程或系统的进行）描述工程或系统的进行 工程可以分为若干个子过程（称为活动），子过程中受条件约束，则可检查是否可顺利进行。有向无环图的检查有向无环图的检查 对无向图，若深度优先搜索中遇到回边则其必定存在环路 对有向图，在深度优先搜索DFS（V）结束之前中遇到回边U到V则

19、的回边，图有也必定有环路。 问题问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 何谓何谓“拓扑排序拓扑排序”？ 按照有向图给出的约束次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。这样若能得到一个全序，则称为拓扑排序。 概念：偏序， 全序，拓朴有序。7.5.1 拓扑排序拓扑排序AOV网：网：顶点表示活动，边表示活动间的优先关系的有向图。 如何进行拓扑排序？如何进行拓扑排序？1. 从有向图中选取一个没有前驱的顶点，并输出之;2. 从有向图中删去

20、此顶点以及所有以它为尾的弧;重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱没有前驱 - 入度为零入度为零删除顶点及以它为尾的弧删除顶点及以它为尾的弧- 弧头顶点的入度减弧头顶点的入度减1例：如图例：如图7.28 P182 问题问题: 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间，问:哪些子工程项是“关键工程”？即:将影响整个工程完成期限的子工程项。整个工程完成的时间为:从有向图的源点到汇点的最长路径。称关键路径关键路径。AOE网网：项点表示事件，边表示活动的网。它是一个带树的有向无环图。“关键活动”指的是: 关键路径上的活动，该弧上的权值增加权值增加

21、 将使有向图上的最长路径的长度增加。最长路径的长度增加。7.5.2 关键路径关键路径“事件(顶点)” 的 最早发生时间最早发生时间 ve(j)ve(j) = 从源点到顶点j的最长路径长度;“事件(顶点)” 的 最迟发生时间最迟发生时间 vl(k) vl(k) = 从顶点k到汇点的最短路径长度;假设第i条弧为则 第i项活动 “活动(弧)”的 最早开始时间 ee(i) ee(i) = ve(j);“活动(弧)”的 最迟开始时间 el(i) el(i) = vl(k) dut(); 如何求关键活动？如何求关键活动？事件发生时间的计算公式:ve(源点) = 0;ve(k) = Maxve(j) + d

22、ut()vl(汇点) = ve(汇点);vl(j) = Minvl(k) dut()求ve的顺序应该是按拓扑有序的次序;求vl的顺序应该是按拓扑逆序的次序; 算法的实现要点算法的实现要点:（1）建立VOE-网的存贮结构（2）从V0出发，ve0=0,按拓朴有序求最旱发生时间（3）从Vn出发，vln=ven,按拓朴逆序求最迟发生时间（4）求活动的最早和最迟发生时间，若有e(s)=l(s),则为关键活动。算法算法7.13,7.14 P184-185例：如图例：如图7.30所示。所示。P185 7.6.1 从某个源点到其余各点的最短路径从某个源点到其余各点的最短路径例：图例：图7.34所示。所示。P187 迪杰斯特拉推出了一个按路径长度递增的次序按路径长度递增的次序求从源点到其余各点最短路径的算法。 假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者 在这条路径上，必定