第七章图17.1 图的基本概念图的基本概念7.1.1图的定义图的定义图中的数据元素称为顶点顶点。在顶点集合V中，第i个顶点记作vi图中两个顶点vi和vj之间有关联关系，称作顶点vi和vj之间有一条边边。在边集合E中，第k条边记作ek=。图图是由顶点的非空有限集合与顶点间关系集合构成的数据结构。记作G=(V,E)。其中，V为顶点集合，E为顶点间关系边的集合。无向图无向图：由没有方向的边构成的图称为无向图。 无向图中的边由顶点的无序偶对组成，因此，在无向图中，顶点偶对与顶点偶对表示同一条边，记作(vi,vj)。2图的定义 有向图有向图：由有方向的边构成的图称为有向图。弧弧：有向图中的边由顶点的有序偶对组成。顶点偶对表示从顶点vi指向顶点vj的一条有向边，也称为弧。顶点vi是有向边的始点，也称为弧尾弧尾。顶点vj是有向边的终点，也称为弧头弧头。 3图的定义 完全图完全图：含有n个顶点和条边的无向图称为完全图。在完全图中，任意两个顶点之间均有边相连推论1：具有n个顶点的无向图最多有条边。有向完全图有向完全图：含有n个顶点和n(n-1)条弧的有向图称为有向完全图。在有向完全图中，任意两个顶点之间均有两条方向相反的弧。推论2：具有n个顶点的有向图最多有n(n-1)条弧。4图的定义邻接点邻接点：在无向图中，若存在一条边(vi, vj)，则称vi和vj互为邻接点。称边(vi, vj)依附于顶点vi和vj或称边(vi, vj)与顶点vi和vj相关联。顶点的度顶点的度：在无向图中，与顶点v相关联的边数称为顶点v的度，记作TD(v)。在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度顶点的入度是指以顶点v为弧头的弧的数目，记作ID(v)；顶点的出度顶点的出度是指以顶点v为弧尾的弧的数目，记作OD(v)。顶点v的度等于顶点v的入度和出度之和，即TD(v)=ID(v)+OD(v)。推论3：对于无向图，其总度数是总边数的两倍。推论4：对于有向图，其总入度、总出度和总边数相等。5图的定义路径路径：在图G中，从顶点vi出发，经过一系列的边或弧能够到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。该路径上所包含的边的数目称为路径长度路径长度简单路径简单路径：若路径上各顶点互不重复，则称这样的路径为简单路径。环环或回路回路：若路径上第一个顶点和最后一个顶点相同，则称这样的路径为环或回路。子图子图：对于图G=V,E和图G=V,E，若存在V V且E E，则称图G是图G的子图。 6图的定义连通图连通图：在无向图中，若从顶点vi到顶点vj有路径存在，则称vi和vj是连通的。如果无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图中的极大连通子图称为该图的连通分量连通分量。 推论5：连通图的连通分量就是它本身。强连通图强连通图：在有向图中，若一对顶点vi和vj（vivj）存在从vi到vj和从vj到vi的有向路径，则称vi和vj是连通的。若有向图中任意两个顶点vi和vj（vivj）之间都是连通的，则称该有向图为强连通图。有向图中的极大强连通子图称为强连强连通分量通分量。 7图的定义权权：图中边或弧上附带的数据称为权。网网：带权的图称为网。 生成树生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接连通图中所有顶点。推论6：有n个顶点的连通图，它的生成树一定包含n个顶点和n-1条边。若加上一条边则构成环，若减去一条边则是非连通图。 87.1.2 图的抽象数据类型 ADT Graph数据元素集合：具有相同性质的称为顶点的有限数据元素集合，以及称为弧或边的有限集合。基本操作：创建图(CreateGraph)：按顶点和弧的定义构造图 查找顶点(LocateVex)：返回指定顶点在图中的位置取顶点值(GetVex)：返回指定顶点的值给顶点赋值(PetVex)：给指定顶点赋值 取第一个邻接点(FirstAdjVex)：取顶点的第一个邻接点取下一个邻接点(NextAdjVex)：取顶点的下一个邻接点插入顶点(InsertVex)：在图中插入新顶点 删除顶点(DeleteVex)：在图中删除指定顶点及相关的弧插入弧(InsertArc)：在图中插入一条新弧删除弧(DeleteArc)：在图中删除指定的弧深度优先遍历(DFSTraverse)：对图进行深度优先遍历广度优先遍历(BFSTraverse)：对图进行广度优先遍历97.2 图的存储结构 7.2.1 邻接矩阵邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。 设G=(V,E)是一个具有n个顶点的图。它的顶点集合V=v0,v1,vn-1，则顶点间的关系E可用如下形式的矩阵A描述。对于A中的每一个元素aij满足：107.2.1 邻接矩阵 【例7-2】对于图7-2（a）所示的无向图，请给出它的邻接矩阵，并根据邻接矩阵计算顶点v2的度。 117.2.1 邻接矩阵 对于带权图（网），邻接矩阵A中的元素定义为：【例7-4】对于图7-5（b）所示的网，请给出它的邻接矩阵。127.2.1 邻接矩阵 用用C语言描述的邻接矩阵语言描述的邻接矩阵：#define MAXVEX 50 /*最大顶点个数*/typedef int weight;/*权值*/typedef structweight arcsMAXVEXMAXVEX;/*邻接矩阵*/DataType dataMAXVEX;/*顶点信息*/int vexs;/*顶点数*/MGraph,*AdjMetrix;137.2.1 邻接矩阵 2.邻接矩阵的操作邻接矩阵的操作（1）创建邻接矩阵）创建邻接矩阵 void CreateGraph(AdjMetrix g,int mMAXVEX,DataType d,int n)int i,j;g-vexs=n;for(i=0;idatai=di;for(j=0;jarcsij=mij; 147.2.1 邻接矩阵 （3）取第一个邻接点）取第一个邻接点int GetFirst(AdjMetrix g,int k)int i;if(kg-vexs) printf(参数k超出范围！n);return -1;for(i=0;ivexs;i+) if(g-arcski=1) return i;return -1; 157.2.1 邻接矩阵 （4）取下一个邻接点）取下一个邻接点 int GetNext(AdjMetrix g,int k,int t)int i;if(kg-vexs | tg-vexs) printf(参数k或t超出范围！n);return NULL;for(i=t+1;ivexs;i+)if(g-arcski=1) return i;return -1; 167.2.1 邻接矩阵 （7）插入边）插入边 void InsertArc(AdjMetrix g,int u,int v,weight w)if(ug-vexs | vg-vexs)printf(参数u或v超出范围！n);return ;g-arcsuv=w; （8）删除边）删除边 void DeleteArc(AdjMetrix g,int u,int v)if(ug-vexs | vg-vexs)printf(参数u或v超出范围！n);return ;g-arcsuv=0; 177.2.2 邻接表 邻接表邻接表是图的链式存储结构。邻接表由边表和顶点表组成边表边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻接点，相当于邻接矩阵中的一行顶点表顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针。顶点表通常采用顺序存储结构。边表的结点结构：adjvex为邻接点在顶点表中的序号，next指向下一个邻接点的指针。顶点表的结点结构：data存放顶点信息，head为边表头指针 逆邻接表逆邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾顶点。 187.2.2 邻接表 C语言描述的邻接表：语言描述的邻接表：#define MAXVEX 50typedef struct arc/*边表结点类型*/int adjvex;/*顶点序号*/struct arc* next;/*指向下一个邻接点*/ArcNode,*PArcNode;typedef struct/*顶点表结点类型*/DataType data;/*顶点信息*/ArcNode* head;/*边表头指针*/VexNode;typedef struct/*邻接表类型*/VexNode listsMAXVEX;/*顶点表*/int edges,vexs;/*边数，顶点数*/VGraph,*AdjList;197.2.2 邻接表 【例7-6】为图7-2（b）所示的图G1建立邻接表和逆邻接表。 207.2.2 邻接表 2.邻接表的操作邻接表的操作（1）创建邻接表）创建邻接表 void CreateGraph(AdjList *g,int mMAXVEX,int n)/*n为顶点总数*/int i,j;PArcNode p;*g=(AdjList)malloc(sizeof(VGraph);/*初始化邻接表*/(*g)-edges=0;(*g)-vexs=n;for(i=0;ilistsi.head=NULL;/*边表头指针初始化*/for(j=n-1;j=0;j-) if(mij!=0) /*矩阵元素不为0，则在边表中生成一个结点*/p=(PArcNode)malloc(sizeof(ArcNode);p-adjvex=j;p-next=(*g)-listsi.head;/*从链表头部插入新结点*/(*g)-listsi.head=p;(*g)-edges+; 217.2.2 邻接表 （3）寻找第一个邻接点）寻找第一个邻接点 int GetFirst(AdjList g,int k)if(kg-vexs) printf(参数k超出范围！n);return -1;if(g-listsk.head=NULL)return -1;elsereturn g-listsk.head-adjvex; 227.2.2 邻接表 （4）寻找下一个邻接点）寻找下一个邻接点 int GetNext(AdjList g,int k,int u)PArcNode p;if(kg-vexs | ug-vexs) printf(参数k或u超出范围！n);return -1;p=g-listsk.head; /*寻找u*/while(p-next!=NULL & p-adjvex!=u) p=p-next; if(p-next=NULL) return -1;else return p-next-adjvex;/*u的next指针域指向下一个邻接点*/ 237.3 图的遍历 7.3.1 深度优先搜索深度优先搜索1.连通图的深度优先搜索遍历连通图的深度优先搜索遍历 （1）遍历方法 从图中指定的顶点v出发，先访问v，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到为止。 【例7-10】从右图所示的无向图的顶点A出发，深度优先搜索遍历图，并写出遍历序列。遍历序列：ABCDEFGH。 247.3.1 深度优先搜索 （2）具体实现）具体实现 以邻接矩阵作为存储结构。建立一个标识数组visited，用于标识顶点是否被访问过。 void DFSTraverse(AdjMetrix g)int i, visitedMAXVEX;for(i=0;ivexs;i+) /*初始化visited数组*/visitedi=0;for(i=0;ivexs;i+)if(visitedi=0)DFS(g,i,visited);257.3.2 广度优先搜索广度优先搜索1.连通图的广度优先搜索遍历连通图的广度优先搜索遍历 （1）遍历方法）遍历方法 从图中指定的顶点v出发，先访问v，再依次访问v的未被访问的所有邻接点wi，然后分别从这些邻接点wi出发依次访问它们的未被访问的所有邻接点tj。依此类推，直至图中所有顶点均被访问过为止 【例7-11】从右图所示的无向图的顶点A出发，广度优先搜索遍历图，并写出遍历序列。 遍历序列：ABHCGDFE。 267.3.2 广度优先搜索广度优先搜索（2）具体实现）具体实现以邻接表作为存储结构。建立一个标识数组visited，用于标识顶点是否被访问过。设置一个队列queue，用于保存访问邻接点的次序。void BFS(AdjList g,int v,int visited)int u, queueMAXVEX; /*循环队列*/int front=0,rear=0; /*队头、队尾指针， int w; /* v的邻接点*/ printf(%d,g-listsv.data); /*访问顶点v*/ visitedv=1;queuerear=v; /*v已被访问过,且入队*/ 277.3.2 广度优先搜索广度优先搜索rear=(rear+1)%MAXVEX;while(frontlistsw.data);visitedw=1;queuerear=w;rear=(rear+1)%MAXVEX;w=GetNext(g,u,w);/*取下一个邻接点*/ 287.3.2 广度优先搜索广度优先搜索2.非连通图的广度优先搜索遍历非连通图的广度优先搜索遍历 void BFSTraverse(AdjList g)int i;int visitedMAXVEX;for(i=0;ivexs;i+) visitedi=0;for(i=0;ivexs;i+) if(visitedi=0)BFS(g,i,visited); 297.3.2 广度优先搜索广度优先搜索【例7-12】对于下图所示的无向图，求：（1）邻接表。（2）按照邻接表，给出从顶点A出发深度优先搜索遍历序列（3）按照邻接表，给出从顶点C出发广度优先搜索遍历序列 深度优先搜索遍历序列：ABCDE。广度优先搜索遍历序列：CABDE。307.4 最小生成树最小生成树 带权图的生成树的边也带权。在这些带权的生成树中必有一颗边的权值之和最小的生成树，这颗生成树就是最小最小（代价）生成树（代价）生成树。 7.4.1 普里姆算法普里姆算法 算法的基本思想： 设G=(V,E)是连通网，V是连通网中顶点集合，E是连通网中边的集合。T=(U,D)是正在构造的最小生成树，U是最小生成树的顶点的集合，D是最小生成树的边的集合。V-U表示属于集合V，但不属于集合U的顶点集合。317.4.1 普里姆算法 （1）若从顶点v0开始构造最小生成树，则从集合V中取出顶点v0放入集合U中。此时，集合U=v0，集合V-U=除v0以外的所有顶点，集合D为空。（2）若在集合U中的顶点vi和集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不构成回路。将顶点vj加入集合U中，将边(vi, vj)加入集合D中。（3）重复步骤（2），直至U与V相等为止。此时，D中必有n-1条边，则T=(U,D)即是最小生成树。【例7-15】已知一个如图所示的带权图，请给出根据普里姆算法构造的一颗最小生成树（假设从顶点1开始构造）。 327.4.1 普里姆算法 337.4.1 普里姆算法 2.具体实现具体实现 设置两个数组lowcost和uset。lowcostv存放集合U中的顶点u和集合V-U中的顶点v构成的权值最小的边(v,u)的权值；uset数组存放U集合中的顶点和V-U集合中的顶点，当usetu=0时，表示顶点u在集合U中，当usetu=1时，表示顶点u在集合V-U中。每次从lowcost数组中寻找权值最小的边。若找到，则把顶点v加入到集合U中，即置usetv为0。当顶点v从集合V-U加入到集合U后，更新lowcostv的权值。若存在一条边(v,u)，它的权值比原先lowcostv的权值小，则用新的权值更新lowcostv。347.4.1 普里姆算法 void Prim(AdjMetrix g,int v)weight lowcostMAXVEX;int usetMAXVEX;int i,j,MinEdge,MinWeight,k;for(i=0;ivexs;i+) /*初始化lowcost和uset数组*/ lowcosti=g-arcsvi;useti=1;usetv=0;/*把起始点放到最小生成树中*/printf(起始点%cn,g-datav); for(i=1;ivexs;i+) 357.4.1 普里姆算法MinWeight=MAXWEIGHT;/*初始化最小权值*/for(j=0;jvexs;j+) if(usetj & lowcostjMinWeight) /*寻找权值最小的边*/MinWeight=lowcostj;MinEdge=j;/*权值最小边的弧尾顶点*/ for(j=0;jvexs;j+)/*寻找权值最小边的弧头顶点*/if(g-arcsjMinEdge=MinWeight) k=j;printf(边(%c,%c)t权值%dn,g-datak,g-dataMinEdge,MinWeight);usetMinEdge=0; v=MinEdge; /*权值最小的边加入最小生成树*/for(j=0;jvexs;j+)/*更新最小权值*/if(usetj & g-arcsvjarcsvj; 367.4.2 克鲁斯卡尔算法1.算法思想：算法思想：2.设G=(V,E)是一个具有n个顶点的带权连通图，T=(U,D)是G的最小生成树。3.初始时，U中包含G的全部n个顶点，D为空。4.从E中选择一条以前未选择过的、边上的权值最小的边加入D中。若加入后，并未使T形成回路，则继续选择下一条边；若加入后，使T形成回路，则放弃选择的边。5.重复以上过程，直至D中包含了n-1条边为止。此时，T即为G的最小生成树。377.4.2 克鲁斯卡尔算法【例7-17】已知一个带权图如图7-14（a）所示，请给出根据克鲁斯卡尔算法构造的一颗最小生成树 387.5 最短路径 7.5.1 从某个顶点到其余顶点的最短路径从某个顶点到其余顶点的最短路径 带权图的路径长度是指路径所经过的所有边上的权值之和。 图的顶点间可能存在多条路径，其中路径长度最短的路径称为最短路径。 最短路径分为两种情况： 从图中某个顶点到其余顶点间的最短路径 图中每对顶点之间的最短路径。 397.5.1 从某个顶点到其余顶点的最短路径从某个顶点到其余顶点的最短路径1.迪杰斯特拉算法迪杰斯特拉算法 （1）初始时，集合V中仅包含源点v，集合W中包含除源点v以外的所有顶点，v到W中各顶点的路径长度或为边的权值（有边相连），或为（没边相连）。（2）按最短路径长度递增的次序，从集合W中选出到顶点v路径长度最短的顶点w，把它加入到集合V中。（3）加入w后，为了寻找下一个最短路径，必须修改从v到集合W中剩余顶点vi的最短路径长度值。若在路径上加入顶点w后，使v到vi的路径长度比原来没有加入v时的路径长度短，则修正v到vi的路径长度为较短者。（4）重复以上过程，直至集合W中的顶点全部加入到集合V中为止。 407.5.1 从某个顶点到其余顶点的最短路径从某个顶点到其余顶点的最短路径【例7-18】已知一个带权图如图所示，请给出从顶点A到图中其余顶点的最短路径。 417.6 拓扑排序和关键路径拓扑排序和关键路径拓扑排序拓扑排序 在有向图中，如果用图中的顶点表示活动（事件、任务），用弧（有向边）表示活动间的先后关系，则称这样的有向图为顶点活动网（Activity On Vertex Network），简称AOV网网。 对于一个AOV网，若存在满足以下性质的一个线性序列：网中的所有顶点都在该序列中。在AOV网中，从顶点vi到顶点vj存在一条路径，则在线性序列中，vi一定排在vj的前面。 则这个线性序列称为拓扑序列。构造拓扑序列的操作称为拓扑排序拓扑排序。 42拓扑排序 拓扑排序的方法：拓扑排序的方法：（1）在有向图中，选择一个入度为0的顶点并输出它。（2）在图中，把该顶点连同它发出的全部有向边一并删除。（3）重复（1）和（2）步骤，直至图中不再有入度为0的顶点为止。【例7-20】已知一个带权图如图所示，请给出图的拓扑有序序列。 43关键路径 在带权有向图中，如果用顶点表示事件，用有向边表示活动，边上的权值表示活动持续的时间，则称这样的有向图为边表示活动的网（Activity On Edge Network），简称AOE网网。对一个只有开始点和一个完成点的工程，可用AOE网来表示。网中仅有一个入度为0的顶点称作源点源点，它表示工程的开始点。同时，网中也仅有一个出度为0的顶点称为汇点汇点，它表示工程的完成点。在AOE网中，从源点到汇点之间可能有多条路径，这些路径中具有最大路径长度的路径称为关键路径关键路径。关键路径上的活动称为关键活动关键活动。 44关键路径 （1）事件的最早发生时间）事件的最早发生时间 vk的最早发生时间se(k)是从源点到顶点vk的最大路径长度。 计算事件vk最早发生时间的递推公式：（2）事件的最迟发生时间）事件的最迟发生时间 vk的最迟发生时间le(k)是在不推迟整个工程工期的前提下，该事件最迟发生的时间。递推公式： 45关键路径 （3）活动的最早开始时间）活动的最早开始时间 若用弧表示活动ai，则根据AOE网的性质，只有事件vk发生了，活动ai才能开始，即活动ai的最早开始时间e(i)等于事件vk的最早发生时间： e(i)=se(k)。 （4）活动的最迟开始时间）活动的最迟开始时间 活动ai的最迟开始时间l(i)是在整个工期按期完工的前提下，ai必须开始的最迟时间。 若用有向边表示活动ai，则活动ai最迟开始时间：46关键路径（5）活动的时间余量）活动的时间余量 活动ai的最迟开始时间l(i)与最早开始时间e(i)之差定义为活动ai的时间余量sp(i)。它表示在不影响整个工程工期的前提下，活动ai可以拖延的时间。 确定关键路径的方法：确定关键路径的方法：求出所有事件的最早发生时间和最迟发生时间；利用它们再求出所有活动的最早开始时间和最迟开始时间；根据活动的时间余量是否为零确定关键活动。关键活动所在的路径就是关键路径。 477.7 综合实例故宫导游咨询 游客游览某一景点时，对景点都不熟悉。特别是对于象故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统，能够为游客提供以下功能：查询景点信息；给出到某个景点的最佳路线；给出到所有景点的最佳路线。 为系统管理员提供以下功能：添加和撤销景点；添加和撤销旅游线路；修改景点信息。 487.7 综合实例故宫导游咨询 分析：分析： 景点和旅游线路可以构成图状结构，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离。查询景点信息就是输出相应顶点的信息；给出到景点的最佳线路就是求最短路径问题；添加和撤销景点、旅游线路就是添加和删除顶点、边；修改景点信息就是修改顶点信息。 497.7 综合实例故宫导游咨询1.数据结构数据结构 2.操作实现操作实现（1）根据景点名称查询景点信息 （2）根据景点名称查找景点序号 （3）显示最短路径 （4）求最短路径 3.主函数主函数 50