第5章〓图论算法 图状结构是一种比树结构更复杂的非线性数据结构。在树结构中,结点间具有分支层次关系,每一层上的结点只能和上一层中的至多一个结点相关,但可能和下一层的多个结点相关。而在图状结构中,任意两个结点之间都可能相关,即结点之间的邻接关系可以是任意的。因此,图状结构被用于描述各种复杂的数据对象,在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用,与之相关的实现算法会影响到许多实际应用问题的算法效率。 随着互联网和物联网的快速发展，未来的世界将会是一个更加智能化、生态化、自动化和便捷化的“万物互联”世界。数字城市、智慧交通、智能医疗等，将现实世界不同领域抽象成一个个的图状结构，利用图的最小生成树算法，可以建设低成本的通信网络和交通网络，进行最佳旅游景点路线规划，优化城市天然气管道铺设布局等； 图的最短路径算法，可以实现最优的物流运输的路径，降低物流成本，还可以应用于自然灾害、矿井、航空等突发事件的应急救援中，以减少生命及财产损失。 观看视频 观看视频 5.1图 5.1.1图的定义和术语 1. 图的定义 图(Graph)由非空的顶点集合和一个描述顶点之间关系——边(或者弧)的集合组成,其形式化定义为 G(V,E) V{vi| vi∈dataobject} E{( vi,vj)| vi, vj ∈V ∧P(vi, vj)} 其中,G表示一幅图； V是图G中顶点的集合； E是图G中边的集合； 集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线,即偶对(vi,vj)表示一条边。图5.1给出了一幅图的示例,在该图中： 集合V{v1,v2,v3,v4,v5} 集合E{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)} 2. 图的相关术语 (1) 无向图。在一幅图中,如果任意两个顶点构成的偶对(vi, vj)∈E是无序的,即顶点之间的连线是没有方向的,则称该图为无向图。如图5.1所示是一幅无向图G1。 (2) 有向图。在一幅图中,如果任意两个顶点构成的偶对(vi, vj)∈E是有序的,即顶点之间的连线是有方向的,则称该图为有向图。如图5.2所示是一幅有向图G2。 G2 (V2,E2) V2{v1,v2,v3,v4} E2{v1,v2,v1,v3,v3,v4,v4,v1} 图5.1无向图G1 图5.2有向图G2 (3) 顶点、边、弧、弧头、弧尾。图中,数据元素vi称为顶点(Vertex); P(vi, vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中,则称这条连线为边; 如果是在有向图中,一般称这条连线为弧。边用顶点的无序偶对(vi, vj)来表示,称顶点vi和顶点vj互为邻接点,边(vi, vj)依附于顶点vi与顶点vj; 弧用顶点的有序偶对vi, vj来表示,有序偶对的第一个结点vi被称为始点(或弧尾),在图中就是不带箭头的一端; 有序偶对的第二个结点vj被称为终点(或弧头),在图中就是带箭头的一端。 (4) 无向完全图。在一幅无向图中,如果任意两个顶点都有一条直接边相连接,则称该图为无向完全图。可以证明,在一幅含有n个顶点的无向完全图中,有n(n1)/2条边。 (5) 有向完全图。在一幅有向图中,如果任意两个顶点之间都有方向互为相反的两条弧相连接,则称该图为有向完全图。在一幅含有n个顶点的有向完全图中,有n(n1)条边。 (6) 稠密图、稀疏图。若一幅图接近完全图,称为稠密图; 称边数很少的图为稀疏图。 (7) 顶点的度、入度、出度。顶点的度(Degree)指依附于某顶点v的边数,通常记为TD(v)。在有向图中,要区别顶点的入度与出度的概念。顶点v的入度指以顶点为终点的弧的数目，记为ID(v); 顶点v的出度指以顶点v为始点的弧的数目,记为OD(v)。有TD(v)ID(v)OD(v)。 例如,在G1中有 TD(v1)2TD(v2)3TD(v3)3TD(v4)2TD(v5)2 在G2中有 ID(v1)1OD(v1)2TD(v1)3 ID(v2)1OD(v2)0TD(v2)1 ID(v3)1OD(v3)1TD(v3)2 ID(v4)1OD(v4)1TD(v4)2 可以证明,对于具有n个顶点、e条边的图,顶点vi的度TD(vi)与顶点的个数以及边的数目满足关系： e∑ni1TD(vi)2 观看视频 (8) 边的权、网图。与边有关的数据信息称为权(Weight)。在实际应用中,权值可以有某种含义。例如,在一幅反映城市交通线路的图中,边上的权值可以表示该条线路的长度或者等级; 对于一幅电子线路图,边上的权值可以表示两个端点之间的电阻、电流或电压值; 对于反映工程进度的图而言,边上的权值可以表示从前一个工程到后一个工程所需要的时间等。边上带权的图称为网图或网络(Network)。如图5.3所示就是一幅无向网图。如果边是有方向的带权图,则就是一幅有向网图。 (9) 路径、路径长度。顶点vp到顶点vq之间的路径(Path)指顶点序列vp,vi1,vi2,…, vim,vq。其中,(vp,vi1),(vi1,vi2),…,(vim,vq)分别为图中的边。路径上边的数目称为路径长度。在图5.1所示的无向图G1中,v1→v4→v3→v5与v1→v2→v5是从顶点v1到顶点v5的两条路径,路径长度分别为3和2。 (10) 回路、简单路径、简单回路。第一个顶点和最后一个顶点相同的路径称为回路或者环(Cycle)。序列中顶点不重复出现的路径称为简单路径。在图5.1中,前面提到的v1到v5的两条路径都为简单路径。除第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,或者简单环。如图5.2中所示的v1→v3→v4→v1。 (11) 子图。对于图G (V,E),G′ (V′,E′),若存在V′是V的子集,E′是E的子集,则称图G′是G的一幅子图。图5.4分别给出了G2和G1的两个子图G′和G″。 (12) 连通的、连通图、连通分量。在无向图中,如果从一个顶点vi到另一个顶点vj(ij)有路径,则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的,则称该图是连通图。无向图的极大连通子图称为连通分量。图5.5(a)中有两个连通分量，如图5.5(b)所示。 图5.3一幅无向网图示意 图5.4图G2和G1的两幅子图示意 (13) 强连通图、强连通分量。对于有向图来说,若图中任意一对顶点vi和vj(ij)均有从一个顶点vi到另一个顶点vj的路径,也有从vj到vi的路径,则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。图5.2中有两个强连通分量,分别是{v1, v3, v4}和{v2},如图5.6所示。 (14) 生成树。所谓连通图G的生成树,指包含G的全部n个顶点的一幅极小连通子图。它必定包含且仅包含G的n1条边。图5.4(b)给出了图5.1中G1的一棵生成树。在生成树中添加任意一条属于原图中的边必定会产生回路,因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边,则必然成为非连通的。 图5.5无向图及连通分量示意 图5.6有向图G2的两个强连通分量示意 (15) 生成森林。在非连通图中,由每个连通分量都可得到一幅极小连通子图,即一棵生成树,这些连通分量的生成树就组成了一幅非连通图的生成森林。 观看视频 5.1.2图的抽象数据类型 图的抽象数据类型定义如下。 ADT Graph{ 数据对象V： V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R： R=｛VR｝。 VR=｛v,w|v,w∈V且P(v,w),v,w表示从v到w的弧,谓词P(v,w)定义了弧v,w的意义或信息｝。 基本操作如下。 (1) CreateGraph(&G,V,VR)： 按V和VR的定义构造图G。 (2) DestroyGraph(&G)： 销毁图G。 (3) Locatevex(G,u)： 若G中存在顶点u,则返回该顶点在图中的位置; 否则返回其他信息。 (4) Getvex(G,v)： 返回顶点v的值。 (5) PutVex(&G,v,value)： 对顶点v赋值value。 (6) FirstAdjVex(G,v)： 返回顶点v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回"空"。 (7) NextAdjVex(G,v,w)： 返回顶点v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回"空"。 (8) InsertVex(&G,v)： 在图G中增添新顶点v。 (9) DeleteVex(&G,v,w)： 删除G中顶点v及其相关的弧。 (10) InsertArc(&G,v,w)： 在G中增添弧v,w,若G是有向的,则还增添对称弧w,v。 (11) DeleteArc(&G,v,w)： 在G中删除弧v,w,若G是有向的,则还删除对称弧w,v。 (12) DFSTraverse(G,Visit())： 对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit（）一次且仅一次。一旦Visit()失败,则操作失败。 (13) BFSTraverse(G,Visit())： 对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit（）一次且仅一次。一旦Visit()失败,则操作失败。 }ADT Graph 观看视频 5.1.3图的存储结构 图是一种结构复杂的数据结构,表现在不仅各顶点的度可以千差万别,而且顶点之间的逻辑关系也错综复杂。从图的定义可知,一幅图的信息包括两部分,即图中顶点的信息以及描述顶点之间的关系(边或者弧的信息)。因此无论采用什么方法建立图的存储结构,都要完整、准确地反映这两方面的信息。 1. 邻接矩阵 邻接矩阵(Adjacency Matrix)的存储结构就是用一维数组存储图中顶点的信息,用矩阵表示图中各顶点之间的邻接关系。如图5.7所示，假设图G(V,E)有n个确定的顶点,即V{v0,v1,…,vn1},则表示G中各顶点相邻关系为一个n×n的矩阵,矩阵的元素为 A［i］［j］ 1，(vi,vj)或vi,vj是E(G)中的边0，(vi,vj)或vi,vj不是E(G)中的边 如图5.8所示，若G是网图,则邻接矩阵可定义为 A［i］［j］ wij，(vi,vj)或vi,vj是E(G)中的边0或∞，(vi,vj)或vi,vj不是E(G)中的边 其中，wij表示边(vi,vj)或vi,vj上的权值; ∞表示一个计算机允许的、大于所有边上权值的数。 图5.7一幅无向图的邻接矩阵表示 图5.8一幅网图的邻接矩阵表示 从图的邻接矩阵存储方法容易看出这种表示具有以下特点。 (1) 无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只需存放上三角(或下三角)矩阵的元素即可。 (2) 对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度TD(vi)。 (3) 对于有向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))。 (4) 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连; 但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。 在用邻接矩阵存储图时,除用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组来存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下。 #define MaxVertexNum 100/*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct { VertexType vexs［MaxVertexNum］; 　　/*顶点表*/ EdgeType edges［MaxVertexNum］［MaxVertexNum］; 　　/*邻接矩阵,即边表*/ int n,e; /*顶点数和边数*/ }MGragh; /*MGragh是以邻接矩阵存储的图类型*/ 建立一幅图的邻接矩阵存储的算法如下。 算法5.1建立有向图的邻接矩阵存储 void CreateMGraph(MGraph *G) { /*建立有向图G的邻接矩阵存储*/ int i,j,k,w; char ch; printf("请输入顶点数和边数(输入格式为:顶点数,边数):＼n"); scanf("%d,%d",&(G->n),&(G->e)); 　　/*输入顶点数和边数*/ printf("请输入顶点信息(输入格式为:顶点号):＼n"); for (i=0;in;i++) scanf("＼n%c",&(G->vexs［i］)); /*输入顶点信息,建立顶点表*/ for (i=0;in;i++) for (j=0;jn;j++) G->edges［i］［j］=0; 　　/*初始化邻接矩阵*/ printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):＼n"); for (k=0;ke;k++) { scanf("＼n%d,%d",&i,&j); /*输入e条边,建立邻接矩阵*/ G->edges［i］［j］=1; /*若加入G->edges［j］［i］=1;,*/ /*则建立完整的无向图邻接矩阵*/ } }/*CreateMGraph*/ 2. 邻接表 邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi,将所有邻接于vi的顶点vj链成一个单链表,这个单链表就称为顶点vi的邻接表,再将所有顶点的邻接表表头放到数组中,就构成了图的邻接表。在邻接表表示中有两种结点结构,如图5.9所示。 一种是顶点表的结点结构,它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成,另一种是边表(即邻接表)结点,它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网图的边表需再增设一个存储边上权值信息的域(info)。网图的边表结构如图5.10所示。 图5.9邻接矩阵表示的结点结构 邻接点域边上权值信息的域指针域 adjvexinfonext 图5.10网图的边表结构 图5.11给出了无向图5.7对应的邻接表表示。 邻接表表示的形式描述如下。 ＃define MaxVerNum 100 /*最大顶点数为100*/ typedef struct node{ /*边表结点*/ int adjvex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指针域*/ /*若要表示边上信息,则应增加一个数据域info*/ }EdgeNode; typedef struct vnode{ /*顶点表结点*/ VertexType vertex; /*顶点域*/ EdgeNode * firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList［MaxVertexNum］; /*AdjList是邻接表类型*/ typedef struct{ AdjList adjlist; /*邻接表*/ int n,e; /*顶点数和边数*/ }ALGraph; /*ALGraph是以邻接表方式存储的图类型*/ 图5.11图的邻接表表示 建立一个有向图的邻接表存储的算法如下。 算法5.2建立有向图的邻接表存储 void CreateALGraph(ALGraph *G) {/*建立有向图的邻接表存储*/ int i,j,k; EdgeNode * s; printf("请输入顶点数和边数(输入格式为:顶点数,边数)： ＼n"); scanf("%d,%d",&(G->n),&(G->e)); /*读入顶点数和边数*/ printf("请输入顶点信息(输入格式为:顶点号)： ＼n"); for (i=0;in;i++) /*建立有n个顶点的顶点表*/ { scanf("＼n%c",&(G->adjlist［i］.vertex)); /*读入顶点信息*/ G->adjlist［i］.firstedge=NULL; /*顶点的边表头指针设为空*/ } printf("请输入边的信息(输入格式为:i,j)： ＼n"); for (k=0;ke;k++) /*建立边表*/ { scanf("＼n%d,%d",&i,&j); /*读入边的顶点对应序号*/ s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新边表结点s*/ s->adjvex=j; /*邻接点序号为j*/ s->next=G->adjlist［i］.firstedge; /*将新边表结点s插入顶点vi的边表头部*/ G->adjlist［i］.firstedge=s; } }/*CreateALGraph*/ 若无向图中有n个顶点、e条边,则它的邻接表需n个头结点和2e个表结点。显然,在边稀疏(e<brcnum),&(*G->arcnum),&IncInfo); /*IncInfo为0则各弧不含信息*/ for (i=0;i<*G->vexnum;++i) /*构造表头向量*/ { scanf(&(G->xlist［i］.vertex)); /*输入顶点值*/ *G->xlist［i］.firstin=NulL;*G->xlist［i］.firstout =NULL; /*初始化指针*/ } for(k=0;kxlist［j］.fistin,*G->xlist［i］.firstout,NULL} /*对弧结点赋值*/ /*{tailvex,headvex,hlink,tlink,info}*/ *G->xlist［j］.fisrtin=*G->xlist［i］.firstout=p; /*完成在入弧和出弧链头的插入*/ if (IncInfo) Input( p->info); /*若弧含有相关信息,则输入*/ } }/*CreateDG*/ 在十字链表中既容易找到以vi为尾的弧,也容易找到以vi为头的弧,因而容易求得顶点的出度和入度(或视需要在建立十字链表的同时求出)。同时,由算法5.3可知,建立十字链表的时间复杂度和建立邻接表是相同的。在某些有向图的应用中,十字链表是很有用的工具。 4. 邻接多重表 邻接多重表(Adjacency Multilist)主要用于存储无向图。因为,如果用邻接表存储无向图,那么每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中,这会给图的某些操作带来不便。例如,对已访问过的边进行标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。 邻接多重表的存储结构和十字链表类似,也是由顶点表和边表组成的,每条边用一个结点表示,其顶点表结点结构和边表结点结构如图5.15所示。 顶点值域指针域 vertexfirstedge (a) 邻接多重表的顶点表结点结构 标记域顶点位置指针域顶点位置指针域边上信息 markivexilinkjvexjlinkinfo (b) 邻接多重表的边表结点结构 图5.15邻接多重表顶点表、边表的结点结构示意 其中,顶点表由两个域组成,vertex域存储和该顶点相关的信息,firstedge域指示第一条依附于该顶点的边。边表结点由6个域组成,mark为标记域,可用于标记该条边是否被搜索过; ivex和jvex为该边依附的两个顶点在图中的位置; ilink指向下一条依附于顶点ivex的边;jlink指向下一条依附于顶点jvex的边； info为指向和边相关的各种信息的指针域。 例如,图5.16所示为无向图5.1的邻接多重表。在邻接多重表中,所有依附于同一顶点的边串联在同一链表中,由于每条边依附于两个顶点,因此每个边结点同时链接在两个链表中。可见,对无向图而言,其邻接多重表和邻接表的差别仅仅在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。因此,除在边结点中增加一个标志域外,邻接多重表所需的存储量和邻接表相同。在邻接多重表上,各种基本操作的实现也和邻接表相似。邻接多重表存储表示的形式描述如下。 #define MAX_VERTEX_NUM 20 typedef emnu{unvisited,visited} VisitIf; typedef struct EBox{ VisitIf mark: /*访问标记*/ int ivex,jvex; /*该边依附的两个顶点的位置*/ struct EBox ilink, jlink; /*分别指向依附这两个顶点的下一条边*/ InfoType info; /*该边信息指针*/ }EBox; typedef struct VexBox{ VertexType data; EBox fistedge; /*指向第一条依附该顶点的边*/ }VexBox; typedef struct{ VexBox adjmulist［MAX_VERTEX_NUM］; int vexnum,edgenum; /*无向图的当前顶点数和边数*/ }AMLGraph; 图5.16无向图G1的邻接多重表 5.2图的遍历算法 图的遍历指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。我国有23个省份、4个直辖市、5个自治区，以及2个特别行政区。34个地区的风土人情各不相同。假如制订一份旅游计划，34个地区全部游玩一遍而且只游玩一次，这就是遍历。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作,图的许多其他操作都是建立在遍历操作的基础之上的。 由于图结构本身的复杂性,图的遍历操作也较复杂,主要表现在以下4方面。 (1) 在图结构中,没有一个“自然”的首结点,图中任意一个顶点都可作为第一个被访问的结点。 (2) 在非连通图中,从一个顶点出发,只能访问它所在的连通分量上的所有顶点,因此,还需考虑如何选取下一个出发点以访问图中其余的连通分量。 (3) 在图结构中,如果有回路存在,那么一个顶点被访问之后,有可能沿回路又回到该顶点。 (4) 在图结构中,一个顶点可以和其他多个顶点相连,当这样的顶点访问过后,存在如何选取下一个要访问的顶点的问题。 图的遍历通常有深度优先搜索和广度优先搜索两种方式,下面分别介绍。 观看视频 5.2.1深度优先搜索 深度优先搜索(Depth First Search，DFS)遍历类似于树的先根遍历,是树的先根遍历的推广。DFS算法最早是由John E.Hopcroft和他的学生Robert E.Tarjan一起提出来的，两位科学家凭借他们在数据结构与图论算法中的贡献共同获得了图灵奖。图灵奖被称为计算机领域的诺贝尔奖，获奖难度很高，但是数据结构领域的很多科学家都获得了图灵奖，因为数据结构领域的这些算法都非常的底层和经典，为后续很多算法和应用奠定了基础，甚至推动了学科领域的发展。 假设初始状态是图中的所有顶点未曾被访问,则深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到; 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。 图5.17一个无向图G5 以图5.17所示的无向图G5为例,进行图的深度优先搜索。假设从顶点v1出发进行搜索,在访问了顶点v1之后,选择邻接点v2。因为v2未曾访问,所以从v2出发进行搜索，以此类推,接着从v4、v8、v5出发进行搜索。在访问了v5之后,由于v5的邻接点都已被访问,因此搜索回到v8。因为同样的理由,搜索继续回到v4、v2直至v1,此时由于v1的另一个邻接点未被访问,因此搜索又从v1到v3,再继续进行下去,由此得到的顶点访问序列为 v1→v2→v4→v8→v5→v3→v6→v7 显然,这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问,需附设访问标志数组visited［0:n1］,其初值为FALSE,一旦某个顶点被访问,则其相应的分量置为TRUE。 从图的某一点v出发,递归地进行深度优先遍历的过程如算法5.4所示。 算法5.4 void DFS(Graph G,int v) { /*从第v个顶点出发递归地深度优先遍历图G*/ visited［v］=TRUE;Visit(v); /*访问第v个顶点*/ for(w=FirstAdjVex(G,v);w; w=NextAdjVex(G,v,w)) if (!visited［w］) DFS(G,w); /*对v的尚未访问的邻接顶点w递归调用DFS算法*/ } 算法5.5和算法5.6给出了对以邻接表为存储结构的整幅图G进行深度优先遍历实现的C语言描述。 算法5.5 void DFSTraverseAL(ALGraph *G) {/*深度优先遍历以邻接表存储的图G*/ int i; for (i=0;in;i++) visited［i］=FALSE; /*标志向量初始化*/ for (i=0;in;i++) if (!visited［i］) DFSAL(G,i); /*vi未访问过,从vi开始深度优先搜索*/ }/*DFSTraverseAL*/ 算法5.6 void DFSAL(ALGraph *G,int i) {/*以vi为出发点对邻接表存储的图G进行深度优先搜索*/ EdgeNode *p; printf("visit vertex:V%c＼n",G->adjlist［i］.vertex); /*访问顶点vi*/ visited［i］=TRUE; /*标记vi已访问*/ p=G->adjlist［i］.firstedge; /*取vi边表的头指针*/ while(p) /*依次搜索vi的邻接点vj,j=p->adjva*/ {if (!visited［p->adjvex］) /*若vj尚未访问,则以vj为出发点向纵深搜索*/ DFSAL(G,p->adjvex); p=p->next; /*找vi的下一个邻接点*/ } }/*DFSAL*/ 分析上述算法,在遍历时,对图中每个顶点至多调用一次DFS函数,因为一旦某个顶点被标记成已被访问,就不再从它出发进行搜索。因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,查找每个顶点的邻接点所需时间复杂度为O(n2),其中n为图中顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间复杂度为O(e),其中e为无向图中的边数或有向图中的弧数。由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(ne)。 观看视频 5.2.2广度优先搜索 广度优先搜索(Breadth First Search，BFS)遍历类似于树的按层次遍历的过程。BFS算法在如今看来并不复杂，但在其刚提出时被大众所接受的过程有一点曲折。它最早是康拉德教授于1945年在他的博士论文里面提出来的，但是这篇博士论文并没有第一时间被奥格斯堡大学发表，直到1972年，也就是又经过了27年，这篇论文手稿才被发表，才有了我们今天看到的BFS算法。 假设从图中某顶点v出发,在访问了v之后依次访问v的各未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程中以v为起始点,由近至远,依次访问和v有路径相通且路径长度为1,2,…的顶点。 例如,对图5.17所示无向图G5进行广度优先搜索遍历,首先访问v1和v1的邻接点v2和v3,然后依次访问v2的邻接点v4、v5及v3的邻接点v6和v7,最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问,并且图中所有顶点都被访问,因此完成了图的遍历。得到的顶点访问序列为 v1→v2→v3→v4→v5→v6→v7→v8 与深度优先搜索类似,在遍历的过程中也需要一个访问标志数组。并且,为了顺次访问路径长度为2,3,…的顶点,需附设队列以存储已被访问的路径长度为1,2,…的顶点。 从图的某一顶点v出发,非递归地进行广度优先遍历的过程如算法5.7所示。 算法5.7 Void BFSTraverse(Graph G, Status(*Visit)(int v)) {/*按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visited*/ for (v=0;vn;i++) visited［i］=FALSE; /*标志向量初始化*/ for (i=0;in;i++) if (!visited［i］) BFSM(G,i); /*vi未访问过,从vi开始BFS搜索*/ }/*BFSTraverseAL*/ 算法5.9 void BFSM(MGraph *G,int k) {/*以vi为出发点,对邻接矩阵存储的图G进行广度优先搜索*/ int i,j; InitQueue(&Q); printf("visit vertex:V%c＼n",G->vexs［k］); /*访问原点vk*/ visited［k］=TRUE; EnQueue(&Q,k); /*原点vk入队列*/ while (!QueueEmpty(&Q)) {i=DeQueue(&Q); /*vi出队列*/ for (j=0;jn;j++) /*依次搜索vi的邻接点vj*/ if (G->edges［i］［j］==1 && !visited［j］)/*若vj未访问*/ {printf("visit vertex:V%c＼n",G->vexs［j］); /*访问vj*/ visited［j］=TRUE; EnQueue(&Q,j); /*访问过的vj入队列*/ } } }/*BFSM*/ 分析上述算法,每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程,因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历图的时间复杂度相同,两者不同之处仅仅在于对顶点访问的顺序不同。 观看视频 5.2.3深度优先搜索与广度优先搜索的应用 例5.1火力网： 炮台的排放问题,图5.18表示了一个4×4的方形城市,其中黑色块是障碍物,白色块是路(空地),黑色圆圈表示炮台安放的位置。布防规则是： 炮台可排放在路上,但任意两个炮台若中间没有障碍物分隔就不能在同一行或同一列中,反之,合法。图5.18中前两种排放合法,后两种则不合法。 图5.18城市炮台的排放 输入文件包含一幅或多幅图的描述,0表示输入结束。每幅图的描述都开始于一个整数n(n≤4),表示城市大小n×n,接下来的n行逐行描述图的信息,“.”表示开放空间,“X”表示墙。请问每次输入一幅城市图之后,最多可以排放几个炮台。［ZOJ 1002］ 输入示例.X..... 4X. X.... .X...X.0 ....3输出示例 XX.....5 .....XX1 2.XX5 XX42 .X....4 3.... 解题思路如下。 由于地图的大小最大为4×4,可将地图用一个char数组存起来,即map［4］［4］。如果map［i］［j］'X'则表示地图此处存放的为墙,map［i］［j］'.'则表示此处存放的为空地,而map［i］［j］'o'则表示此处存放的为炮台。关键是炮台不能同时在水平和垂直线上,除非有墙作为间隔。定义k为位置,k0即为地图左上方第一个格子(见图5.19)。 0123 4567 891011 12131415 图5.19位置地图 依次往其中放炮台,需判断两个条件。 (1) 放的位置是否为空地。 (2) 同行同列不能有炮台,除非有墙间隔(见canput函数)。 如果到了kn*n，即终止条件时,看目前的最大炮台数是否大于bestn最优炮台数。 如此搜索,即可得到最好的结果。算法如下。 算法5.10 #include int n; 　　//城市的尺寸 char map［4］［4］; 　　//城市的地图,最多是4×4 int bestn; 　　//最多放的炮台数 int canput(int row,int col) 　　//看炮台是否能够放置 {int i; for(i=row-1;i>=0;i--) 　　//扫描行 {if(map［i］［col］=='X') {break; } if(map［i］［col］=='o') {return 0; } } for(i=col-1;i>=0;i--) 　　//扫描同一列 {if(map［row］［i］=='X') {break; } if(map［row］［i］=='o') {return 0; } } return 1; } void backtrack(int k,int current) 　　//current为放的数目,k为放置炮台的位置0,1,2,3,…,n×n {int x,y; if(k>=n*n) 　　//到达最后一个 {if(current>bestn) {bestn=current; } return; } else {x=k/n; 　　//计算x坐标 y=k%n; 　　//计算y坐标 if(map［x］［y］=='.'&&canput(x,y)) {map［x］［y］='o'; 　　//安放炮台 backtrack(k+1,current+1); 　　//进入下一个坐标,数目加1 map［x］［y］='.'; 　　//还原 } backtrack(k+1,current); } } void initial() {int i,j; for(i=0;i<4;i++) {for(j=0;j<4;j++) {map［i］［j］='.'; } } } int main() {scanf("%d",&n); while(n) {int i,j; bestn=0; initial(); for(i=0;i int n; 　　//n表示游戏的大小,n小于或等于5 int element［25］［4］; 　　//存放每个格子 int state［25］; 　　//每个状态 int result［25］; 　　//存放的结果 int q; 　　//状态的个数 void initial() 　　//初始化 {int i,j; for(i=0;i<25;i++) {for(j=0;j<4;j++) {element［i］［j］=0; } state［i］=0; result［i］=0; } q=0; } int backtrack(int ipos) 　　//搜索到ipos位 {int i; if(ipos==n*n) 　　//成功放完n*n个square {return 1; } else {for(i=0;i=n) //判断能否符合要求： 不是最上边的 {if(element［result［ipos-n］］［2］!=element［i］［0］) {continue; } } if(ipos%n!=0) //不是最左边的 {if(element［result［ipos-1］］［1］!=element［i］［3］) {continue; } } state［i］--; result［ipos］=i; if(backtrack(ipos+1)==1) 　　//DFS的精髓 return 1; state［i］++; 　　//恢复该方块的类型数1 个,便于下一次搜索 } } } return 0; } int main() {int i,j,index; index=0; int top,right,bottom,left; scanf("%d",&n); while(n) {initial(); index++; for(i=0;i1) {printf("＼n"); //陷阱！就是每个结果之间要有空白行 } printf("Game %d: ",index); if(backtrack(0)) {printf("Possible＼n"); } else {printf("Impossible＼n"); } scanf("%d",&n); } return 0; } 题目要求样例的解之间要用空行分隔,但最后一个样例的解之后就不应有多余的空行。 1359 2194 74 3526 65 7834 41 9258 8417 图5.21数独表 例5.3数独游戏： 数独游戏是一种非常流行的填数游戏。要求用1~9的数字去填充如图5.21所示的9×9表格,具体要求如下。 (1) 每行的9个格子中1~9各出现一次。 (2) 每列的9个格子中1~9各出现一次。 (3) 用粗线隔开的3×3的小块的9个格子中1~9个数字也各出现一次。 输入数据首先是给出测试用例数,然后是表相关的9行数据,每行9个十进制数字,0表示该位置是空的。对每个测试用例按照输入数据的格式输出解,并在空白处填入符合规则的数字。如果解不唯一,只要输出其中一种即可。［POJ 2676］ 输入示例输出示例 1143628579 103000509572139468 002109400986754231 000704000391542786 300502006468917352 060000050725863914 700803004237481695 000401000619275843 009205800854396127 804000107 解题思路如下。 本题求解需要使用回溯法、DFS算法,并使用标记法剪枝。下面说说剪枝。 (1) 如果有一个格子,9个数都不能填进去,剪枝。如果只能填一个,不用说,直接填。 (2) 如果有这么一行,有一个数放到9个格子里面的任一个都不可,剪枝。如果只有一个格子可填该数,直接填。 (3) 如果有这么一列,有一个数放到9个格子里面的任一个都不可,剪枝。如果只有一个格子可填该数,直接填。 (4) 如果有这么一个九宫格,有一个数放到9个格子里面的任一个都不可,剪枝。如果只有一个格子可填该数,直接填。 参考算法如下。 算法5.12 #include #include bool rUsed［9］［10］,cUsed［9］［10］,sUsed［9］［10］; //用于标记某行、某列、某个3×3小方格上哪些数字已经被使用过了 int pos［100］; 　　//还没有填充数字的方格位置 int nullNum; 　　//空白的个数,即需填数字个数 int table［9］［9］; bool DFS_SUDO; void print() 　　//输出结果表 { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) printf("%d",table［i］［j］); printf("＼n"); } } void DFS(int n) { if (n>=nullNum) 　　//已填写数字个数大于或等于空白数 { DFS_SUDO=true; 　　//递归结束 print(); 　　//调用print函数输出结果 return; } int r=pos［n］/9; 　　//在第r行 int c=pos［n］%9; 　　//在第c列 int k=(r/3)*3+(c/3); 　　//在第k个小方格 for(int i=1; i<=9 && !DFS_SUDO;i++) { if (cUsed［c］［i］) continue; 　　//判别列中是否用过该数字 if (rUsed［r］［i］) continue; 　　//判别行中是否用过该数字 if (sUsed［k］［i］) continue; 　　//判别方格中是否用过该数字 cUsed［c］［i］=rUsed［r］［i］=sUsed［k］［i］=true; //置已用数字标志 table［r］［c］=i; 　　//当前位置填上数字i DFS(n+1); 　　//递归找下一个要填数的位置 table［r］［c］=0; //如果DFS失败就回溯,并还原原来的值 cUsed［c］［i］=rUsed［r］［i］=sUsed［k］［i］=false; //还原标志位的值 } return; } int main() { FILE *fp; int testCase; char line［10］; fp=fopen("test.txt","r"); //以文件形式打开测试文件 //testCase = fgetc(fp)-'0'; fscanf(fp,"%d",&testCase); 　　//输入测试的数据组数 fgetc(fp); 　　//输入一行结束符 while(testCase--) { nullNum=0; for(int i=0;i<9;i++) //初始化标志位 for(int j=0;j<10;j++) rUsed［i］［j］=cUsed［i］［j］=sUsed［i］［j］=false; for(int i=0;i<9;i++) { fgets(line,11,fp); //读入一行 for(int j=0;j<9;j++) { table［i］［j］=line［j］-'0'; if(table［i］［j］){ rUsed［i］［table［i］［j］］=true; //第i行用过这个数 cUsed［j］［table［i］［j］］=true; //第j列用过这个数 int k=(i/3)*3 + (j/3); //第k个3×3方格 sUsed［k］［table［i］［j］］=true; //第k个方格用过这个数 } else pos［nullNum++］=9*i+j; //使用数组,记录没有填数的小方格的位置 } } DFS_SUDO=false; DFS(0); } fclose(fp); return 0; } 使用二维数组直接把已经存在的数字和没有填数字的位置用数组记录下来,这样在DFS时就非常方便,所以,选择合适和便于处理的数据结构有事半功倍的效果。建议读者再重新去思考和理解一下第2章中介绍的迷宫问题算法。 5.3图的连通性 利用图的遍历算法可以判定一幅图的连通性。本节将重点讨论无向图的连通性、有向图的连通性、由图得到其生成树或生成森林以及连通图中是否有关结点等几个有关图的连通性的问题。 观看视频 5.3.1无向图的连通性 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对于非连通图,则需从多个顶点出发进行搜索,而在每一次从一个新的起始点出发进行搜索的过程中得到的顶点访问序列恰为其各连通分量中的顶点集。例如,图5.5(a)是一幅非连通图G3,对其邻接表(见图5.22)进行深度优先搜索遍历,并调用两次深度优先搜索(即分别从顶点A和C出发),得到的顶点访问序列分别为A B F E和C D,这两个顶点集分别加上遍历时所依附于这些顶点的边,便构成了非连通图G3的两个连通分量,如图5.5(b)所示。 图5.22G3的邻接表 因此,要想判定一幅无向图是否为连通图,或有几个连通分量,就可设一个计数变量count,初始时取值为0,在算法5.5的第二个for循环中,每调用一次深度优先搜索,就给count增1。这样,当整个算法结束时,依据count的值,就可确定图的连通性了。 5.3.2有向图的连通性 深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构,则求强连通分量的步骤如下。 (1) 在有向图G上,从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历,并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。此时需对5.2.1节中的算法进行如下两点修改： ①在进入DFSTraverseAL函数时首先进行计数变量的初始化,即在入口处加上count0的语句; ②在退出函数之前将完成搜索的顶点号记录在另一个辅助数组finished［vexnum］中,即在DFSAL函数结束之前加上finished［count］v的语句。 (2) 在有向图G上,从最后完成搜索的顶点(即finished［vexnum1］中的顶点)出发,沿着以该顶点为头的弧进行逆向的深度搜索遍历,若此次遍历不能访问到有向图中的所有顶点,则从余下的顶点中最后完成搜索的那个顶点出发,继续进行逆向的深度优先搜索遍历,以此类推,直至有向图中所有顶点都被访问到为止。此时调用DFSTraverseAL函数需进行如下修改： 函数中第二条循环语句的边界条件应改为v从finished［vexnum1］至finished［0］。 由此,每次调用DFSAL函数进行逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集。 例如图5.14(a)所示的有向图,假设从顶点v1出发进行深度优先搜索遍历,得到finished数组中的顶点号为(1,3,2,0),则再从顶点v1出发进行逆向的深度优先搜索遍历,得到两个顶点集{v1,v3,v4}和{v2},这就是该有向图的两个强连通分量的顶点集。 上述求强连通分量的第(2)步,其实质如下。 (1) 构造一幅有向图Gr,设G (V,{A}),则Gr (Vr,{Ar})对于所有vi,vj∈A,必有vj,vi∈Ar。即Gr中拥有和G方向相反的弧。 (2) 在有向图Gr上,从顶点finished［vexnum1］出发进行深度优先遍历。可以证明,在Gr上所得深度优先生成森林中每棵树的顶点集即为G的强连通分量的顶点集。 显然,利用遍历求强连通分量的时间复杂度亦和遍历相同。 观看视频 5.3.3生成树和生成森林 本节将给出通过对图的遍历,得到图的生成树或生成森林的算法。 设E(G)为连通图G中所有边的集合,则从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T(G)和B(G),其中T(G)是遍历图过程中历经的边的集合; B(G)是剩余边的集合。显然,T(G)和图G中所有顶点一起构成连通图G的极小连通子图。按照5.1.2节的定义,它是连通图的一棵生成树,并且由深度优先搜索得到的为深度优先生成树; 由广度优先搜索得到的为广度优先生成树。例如,图5.23(a)和图5.23(b)所示分别为连通图G5的深度优先生成树和广度优先生成树，图中虚线为集合B(G)中的边,实线为集合T(G)中的边。 图5.23由图5.17无向图G5得到的生成树 对于非连通图,通过这样的遍历,将得到的是生成森林。例如,图5.24(b)所示为图5.24(a)的深度优先生成森林,它由3棵深度优先生成树组成。 图5.24非连通图G6及其生成森林 假设以孩子兄弟链表作生成森林的存储结构,则算法5.13生成非连通图的深度优先生成森林,其中DFSTree函数如算法5.14所示。显然,算法5.13的时间复杂度和遍历相同。 算法5.13 void DFSForest(Graph G, CSTree *T) { /*建立无向图G的深度优先生成森林的孩子兄弟链表T*/ T=NULL; for (v=0;vnextsibling=p; /*前一棵的根的兄弟是其他生成树的根*/ q=p; /*q指示当前生成树的根*/ DFSTree(G,v,&p); /*建立以p为根的生成树*/ } } 算法 5.14 void DFSTree(Graph G,int v,CSTree *T) {　　/*从第v个顶点出发深度优先遍历图G,建立以*T为根的生成树*/ visited［v］=TRUE; first=TRUE; for(w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w)) if(!visited［w］) {p=(CSTree)malloc(sizeof)CSNode)); /*分配孩子结点*/ *p={GetVex(G,w),NULL,NULL}; if (first) /*w是v的第一个未被访问的邻接顶点,作为根的左孩子结点*/ {T->lchild=p; first=FALSE; } else 　　/*w是v的其他未被访问的邻接顶点,作为上一邻接顶点的右兄弟*/ {q->nextsibling=p; } q=p; DFSTree(G,w,&q); /*从第w个顶点出发深度优先遍历图G,建立生成子树*q*/ } } 观看视频 5.3.4关节点和重连通分量 假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(Articulation Point)。一幅没有关节点的连通图称为重连通图(Biconnected Graph)。在重连通图上,任意一对顶点之间至少存在两条路径,因此在删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性。若在连通图上至少删去k个顶点才能破坏图的连通性,则称此图的连通度为k。关节点和重连通图在实际中有较多应用。显然,一幅表示通信网络的图的连通度越高,其系统越可靠,无论是哪一个站点出现故障或遭到外界破坏,都不影响系统的正常工作; 又如,一个航空网若是重连通的,则当某条航线因天气等某种原因关闭时,旅客仍可从其他航线绕道而行; 再如,若将大规模的集成电路的关键线路设计成重连通图,则在某些元件失效的情况下,整个片子的功能不受影响,反之,在战争中,若要摧毁敌方的运输线,仅需破坏其运输网中的关节点即可。 例如,图5.25(a)中图G7是连通图,但不是重连通图。图中有3个关节点A、B和G。若删去顶点B以及所有依附顶点B的边,G7就被分割成3个连通分量{A、C、F、L、M、J}、{G、H、I、K}和{D、E}。类似地,若删去顶点A或G以及所依附于它们的边,则G7被分割成两个连通分量,由此,关节点亦称为割点。 图5.25无向连通图G7及其生成树 利用深度优先搜索便可求得图的关节点,并由此可判别图是否是重连通的。 图5.25(b)所示为从顶点A出发深度优先生成树,图中实线表示树边,虚线表示回边(即不在生成树上的边)。对树中任一顶点v而言,其孩子结点为在它之后搜索到的邻接点,而其双亲结点和由回边连接的祖先结点是在它之前搜索到的邻接点。由深度优先生成树可得出两类关节点的特性。 (1) 若生成树的根有两棵或两棵以上的子树,则此根顶点必为关节点。因为图中不存在连接不同子树中顶点的边,因此,若删去根顶点,生成树便变成生成森林，如图5.25(b)中所示的顶点A。 (2) 若生成树中某个非叶结点v,其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边,则v为关节点。因为,若删去v,则其子树和图的其他部分被分割开来，如图5.25(b)所示的顶点B和G。 若对图Graph(V,{Edge})重新定义遍历时的访问函数visited,并引入一个新的函数low,则由一次深度优先遍历便可求得连通图中存在的所有关节点。 定义visited［v］为深度优先搜索遍历连通图时访问顶点v的次序号; 定义： low(v)Minvisited［v］,low［w］,visited［k］w是v在DFS生成树上的孩子结点;k是v在DFS生成树上由回边联结的祖先结点;(v,w)∈Edge;(v,k)∈Edge。 若对于某个顶点v,存在孩子结点w且low［w］≥visited［v］,则该顶点v必为关节点。因为当w是v的孩子结点时,low［w］≥visited［v］,表明w及其子孙均无指向v的祖先的回边。 由定义可知,visited［v］值即为v在深度优先生成树的前序序列的序号,只需将DFS函数中头两条语句改为visited［v0］count(在DFSTraverse中设初值count1)即可; low［v］可由后序遍历深度优先生成树求得,而v在后序序列中的次序和遍历时退出DFS函数的次序相同,由此修改深度优先搜索遍历的算法便可得到求关节点的算法(如算法5.15和算法5.16所示)。 算法 5.15 void FindArticul(ALGraph G) { /*连通图G以邻接表作存储结构,查找并输出G上的全部关节点*/ count=1; /*全局变量count用于对访问计数*/ visited［0］=1; /*设定邻接表上0号顶点为生成树的根*/ for(i=1;iadjvex; DFSArticul(g,v); /*从顶点v出发深度优先查找关节点*/ if(countnext) { p=p->next; v=p->adjvex; if(visited［v］==0) DFSArticul(g,v); } } } /*FindArticul*/ 算法 5.16 void DFSArticul(ALGraph G,int v0) /*从顶点v0出发深度优先遍历图G,查找并输出关节点*/ { visited［v0］min=++count; /*v0是第count个访问的顶点*/ for(p=G.adjlist［v0］.firstedge; p; p=p->next;) /*对v0的每个邻接点检查*/ { w=p->adjvex; /*w为v0的邻接点*/ if(visited［w］==0) /*若w未曾访问,则w为v0的孩子*/ { DFSArticul(G,w); /*返回前求得low［w］*/ if(low［w］=visited［v0］) printf(v0,G.adjlist［v0］.vertex); /*输出关节点*/ } else if(visited［w］next) 　　//对所有可达边进行搜索 {v = e->t; if (!DFN［v］) 　　//用来更新Low［u］ {tarjan(v); if (Low［v］ #include #include #include #include using namespace std; const int Max=1010; int top［Max］,edge［Max］［Max］;　　//memset(top,0,sizeof(top)); int dfsNum［Max］,dfsnum;　　//memset(dfsNum,0,sizeof(dfsNum)),dfsNum=1; int low［Max］,degree［Max］, cc［Max］; int ccCnt, ans; bool exist［Max］［Max］; void tarjan(int a,int fa) {dfsNum［a］=low［a］=++dfsnum; for(int i=0;ilow［edge［a］［i］］) low［a］=low［edge［a］［i］］; if(dfsNum［a］dfsNum［edge［a］［i］］) low［a］=dfsNum［edge［a］［i］］; } } } void dfs(int fa, int u) {cc［u］ = ccCnt; for(int i=0; iadjlist［i］.count == 0) {G->adjlist［i］.count = top; top = i; } } for (i=0;iadjlist［top］.count; /*从栈中退出一个顶点并输出*/ printf("% c",G->adjlist［j］.vertex); ptr=G->adjlist［j］.firstedge; while (ptr!=null) {k=ptr->adjvex; G->adjlist［k］.count--; /*当前输出顶点邻接点的入度减1*/ if(G->adjlist［k］.count==0) /*新的入度为0的顶点进栈*/ {G->adjlist［k］.count=top; top=k; } ptr=ptr->next; /*找到下一个邻接点*/ } } } 对一个具有n个顶点、e条边的网来说,整个算法的时间复杂度为O(en)。 观看视频 5.4.3AOE网与关键路径 1. AOE(Activity On Edge)网 若在带权的有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示活动的开销(如该活动持续的时间),则此带权的有向图称为AOE网。 如果用AOE网来表示一项工程,那么,仅仅考虑各子工程之间的优先关系还不够,更多的是关心整个工程完成的最短时间是多少; 哪些活动的延期将会影响整个工程的进度,而加速这些活动是否会提高整个工程的效率。因此,通常在AOE网中列出完成预定工程计划所需要进行的活动,每个活动计划完成的时间,要发生哪些事件以及这些事件与活动之间的关系,从而可以确定该项工程是否可行,估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 AOE网具有以下两个性质。 (1) 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 (2) 只有在进入一某顶点的各有向边所代表的活动都已经结束时,该顶点所代表的事件才能发生。 图5.34给出了一个具有15个活动、11个事件的假想工程的AOE网。v1,v2,…,v11分别表示一个事件; v1,v2,v1,v3,…,v10,v11分别表示一个活动; 用a1,a2,…,a15代表这些活动。其中,v1称为源点,是整个工程的开始点,其入度为0; v11为终点,是整个工程的结束点,其出度为0。 图5.34一个AOE网实例 对于AOE网,可采用与AOV网一样的邻接表存储方式。其中,邻接表中边结点的域为该边的权值,即该有向边代表的活动所持续的时间。 2. 关键路径 由于AOE网中的某些活动能够同时进行,因此完成整个工程所必须花费的时间应该为源点到终点的最大路径长度(这里的路径长度指该路径上的各活动所需时间之和)。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。这就是说,要缩短整个工期,必须加快关键活动的进度。 利用AOE网进行工程管理时需要解决的主要问题如下。 (1) 计算完成整个工程的最短路径。 (2) 确定关键路径,以找出哪些活动是影响工程进度的关键。 3. 关键路径的确定 为了在AOE网中找出关键路径,需要定义几个参量,并且说明其计算方法。 1) 事件的最早发生时间ve［k］ ve［k］指从源点到顶点的最大路径长度代表的时间。这个时间决定了所有从顶点发出的有向边所代表的活动能够开工的最早时间。根据AOE网的性质,只有进入vk所有活动vj,vk都结束时,vk代表的事件才能发生; 而活动vj,vk的最早结束时间为ve［j］dut(vj,vk)。所以计算vk发生的最早时间的方法如下： ve［l］0 ve［k］Max{ve［j］dut(vj,vk)}，vj,vk∈p［k］(5.1) 其中,p［k］表示所有到达vk的有向边的集合; dut(vj,vk)为有向边vj,vk上的权值。 观看视频 2) 事件的最迟发生时间vl［k］ vl［k］指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。设有向边vk,vj代表从vk出发的活动,为了不拖延整个工期,vk发生的最迟时间必须保证不推迟从事件vk出发的所有活动vk,vj的终点vj的最迟时间vl［j］。vl［k］的计算方法如下： vl［n］ve［n］ vl［k］Min{vl［j］dut(vk,vj)}，vk,vj∈s［k］(5.2) 其中,s［k］为所有从vk发出的有向边的集合。 3) 活动ai的最早开始时间e［i］ 若活动ai由弧vk,vj表示,根据AOE网的性质,只有事件vk发生了,活动ai才能开始。也就是说,活动ai的最早开始时间应等于事件vk的最早发生时间。因此,有 e［i］ve［k］(5.3) 4) 活动ai的最晚开始时间l［i］ 活动ai的最晚开始时间指在不推迟整个工程完成日期的前提下,必须开始的最晚时间。若由弧vk,vj表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此,应该有 l［i］vl［j］dut(vk,vj)(5.4) 根据每个活动的最早开始时间e［i］和最晚开始时间l［i］就可判定该活动是否为关键活动,也就是那些l［i］e［i］的活动就是关键活动,而那些l［i］e［i］的活动则不是关键活动,l［i］e［i］的值为活动的时间余量。关键活动确定之后,关键活动所在的路径就是关键路径。 以图5.35所示的AOE网为例,求出上述参量,确定该网的关键活动和关键路径。 首先,按照式(5.1)求事件的最早发生时间ve［k］。 ve(1)0ve(7)max{ve(4)6,ve(5)8}15 ve(2)3ve(8)ve(5)411 ve(3)4ve(9)max{ve(8)10,ve(6)2}21 ve(4)ve(2)25ve(10)max{ve(8)4,ve(9)1}22 ve(5)max{ve(2)1,ve(3)3}7ve(11)max{ve(7)7,ve(10)6}28 ve(6)ve(3)59 其次,按照式(5.2)求事件的最迟发生时间vl［k］。 vl(11) ve(11)28vl(5)min{vl(7)8,vl(8)4}7 vl(10) vl(11)622vl(4) vl(7)615 vl(9)vl(10)121vl(3)min{vl(5)3, vl(6)5}4 vl(8)min{vl(10)4, vl(9)10}11vl(2)min{vl(4)2,vl(5)1}6 vl(7)vl(11)721vl(1)min{vl(2)3, vl(3)4}0 vl(6) vl(9)219 再按照式(5.3)和式(5.4)求活动ai的最早开始时间e［i］和最晚开始时间l［i］。 a1e(1)ve(1)0l(1)vl(2) 3 3 a2e(2)ve(1)0l(2)vl(3) 40 a3e(3)ve(2)3l(3)vl(4) 213 a4e(4)ve(2)3l(4)vl(5) 16 a5e(5)ve(3)4l(5)vl(5) 34 a6e(6)ve(3)4l(6)vl(6) 514 a7e(7)ve(4)5l(7)vl(7) 615 a8e(8)ve(5)7l(8)vl(7) 813 a9e(9)ve(5)7l(9)vl(8) 47 a10e(10)ve(6)9l(10)vl(9) 219 a11e(11)ve(7)15l(11)vl(11) 721 a12e(12)ve(8)11l(12)vl(10) 418 a13e(13)ve(8)11l(13)vl(9) 1011 a14e(14)ve(9)21l(14)vl(10) 121 a15e(15)ve(10)22l(15)vl(11) 6 22 最后,比较e［i］和l［i］的值可判断出a2,a5,a9,a13,a14,a15是关键活动,关键路径如图5.35所示。 图5.35一个AOE网实例 由上述方法得到求关键路径的算法步骤如下。 (1) 输入e条弧j,k,建立AOE网的存储结构。 (2) 从源点v0出发,令ve［0］0,按拓扑有序求其余各顶点的最早发生时间ve［i］(1≤i≤n1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止; 否则执行步骤(3)。 (3) 从汇点vn出发,令vl［n1］ve［n1］,按逆拓扑有序求其余各顶点的最迟发生时间vl［i］(n2≥i≥2)。 (4) 根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)l(s),则为关键活动。 由该步骤得到的算法如算法5.21和算法5.22所示。在算法5.21中,Stack为栈的存储类型; 引用的函数FindInDegree(G,indegree)用来求图G中各顶点的入度,并将所求的入度存放于一维数组indegree中。 算法5.21 int topologicalOrder(ALGraph G,Stack T) { /*有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve(全局变量)*/ /*T为拓扑序列顶点栈,S为零入度顶点栈*/ /*若G无回路,则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR*/ FindInDegree(G, indegree); /*对各顶点求入度indegree［0..vernum-1］*/ InitStack(S); /*建立入度顶点栈S*/ count = 0; ve［0..G.vexnum-1］ = 0; /*初始化ve［ ］*/ for (i=0; inext) {k = p->adjvex; /*对j号顶点的每个邻接点的入度减1*/ if(-- indegree［k］ == 0) Push(S,k); /*若入度减为0, 则入栈*/ if (ve［j］+* (p->info)>ve［k］) ve［k］ = ve［j］+*(p->info); } } if (countnext) {k=p->adjvex; dut = * (p->info); if (vl［k］-dutnext) {k = p->adjvex; dut= * (p->indo); e = ve［j］; l = vl［k］ - dut; tag = (e==l) ? '*':'' ; printf(j,k,dut,e,l,tag); /*输出关键活动*/ } return 1; /*求出关键活动后返回1*/ } /*Criticalpath*/ 观看视频 5.5最短路径算法 最短路径问题是图的又一个比较典型的应用问题。例如,某一地区的一个公路网,给定了该网内的n个城市以及这些城市之间的相通公路的距离,能否找到城市A到城市B之间一条距离最近的通路呢？如果将城市用点表示,城市间的公路用边表示,公路的长度作为边的权值,那么,这个问题就可归结为在网图中,求点A到点B的所有路径中,边的权值之和最短的那一条路径。这条路径就是两点之间的最短路径,并称路径上的第一个顶点为源点(Sourse),最后一个顶点为终点(Destination)。在非网图中,最短路径指两点之间经历的边数最少的路径。 输入一幅赋权图： 与每条边(vi,vj)相联系的是穿越该弧的代价(或称为值)ci,j,一条路径v1,v2,…,vn,的值是∑n1i1ci,i1,叫作赋权路径长度(Weighted Path Length)。而无权路径长度(Unweighted Path Length)只是路径上的边数,即n1。 单源最短路径问题： 给定一幅带权图G (V, E)和一个特定顶点s作为输入,找到s到G中每个其他顶点的最短带权路径。 例如图5.36(a)中,从v1到v6的最短带权路径长度为6,它是从v1到v4到v7再到v6的路径。这两个顶点间的最短无权路径长度为2。图5.36(b)给出了一条权值为负数的边,从v5到v4的路径长度为1,但通过循环v5,v4,v2,v5,v4存在一条最短路径,其值为5,其实这条路径仍然不是最短的,因为循环可以进行多次,因此,这两个顶点间的最短路径问题是不确定的。类似地，v1到v6的最短路径也是不确定的,因为它可以进入同样的循环，这个循环叫负值环(Negative Cost Cycle); 当它出现在图中时,最短路径问题就是不确定的。有带负值的边未必就是坏事,但它的出现似乎使问题增加了难度。 图5.36带权有向图和带负值权的有向图 本节重点介绍单源最短路径问题的相关算法。首先,考虑无权最短路径问题,并指出如何以O(|E||V|)时间解决它。其次,假设边无负值,如何求解带权最短路径问题,期望在使用合理数据结构实现时的运行时间为O(|E|·log2|V|)。如果图有负边,介绍一个时间界为O(|E|·|V|)的简单解法。 5.5.1无权最短路径 显然无权图可以视为权值都为1的带权图的特殊情形,如可将图5.36（a）视为一幅权值均为1的无权图G。使用某个顶点s作为输入参数,要找出从s到所有其他顶点的最短路径。假设选择s为v3,则s到v3的最短路径为0,下一步可以通过v3找到路径长度为1的顶点v1和v6,再通过v1和v6找出路径长度为2的顶点v2和v4,最后通过v2、v4找出其余顶点的路径长度均为3。显然,这个方法就是BFS,处理过程类似于树的层次遍历,其时间复杂度为O(|E||V|)。下面简要说明算法的实现。 对于每个顶点,关注顶点是否被处理(未处理为F,处理过为T,初始为F),s到此顶点的路径长dv(s初始为0,其他为INFINITY)。在任意时刻,只存在两种类型的未知顶点,一些顶点的dvcurrDist,另一些顶点的dvcurrDist1。一种抽象是保留两个盒子,1号盒子装有dv currDist的那些未知顶点,而2号盒子装有dv currDist 1的那些顶点。找出一个合适顶点的测试可以用查找1号盒内的任意顶点v代替。在更新v的临界顶点w后,将w放入2号盒中。 可以使用一个队列进一步简化上述模型。迭代开始时,队列只含有距离为currDist的顶点。当添加距离为currDist1的那些邻接顶点时,由于它们自队尾入队,因此保证它们直到所有距离为currDist的顶点都被处理之后才处理。下面给出无权最短路径问题的伪代码。 算法5.23 void unweighted(Vertex s) {Queueq = new Queue(); //一个队列 for each Vertex v 　　//每个顶点初始距离为INFINITY v.dist = INFINITY; s.dist = 0; 　　//s初始距离为0 q.enqueue(s); while(!q.isEmpty()) {Vertex v = q.dequeue(); for each Vertex w adjacent to v 　　//遍历v的邻接顶点 if(w.dist == INFINITY) 　　//如果dist是INFINITY说明没有处理过 {w.dist = v.dist + 1; w.path = v; q.enqueue(w); } } } 观看视频 5.5.2Dijkstra算法 Dijkstra算法是由迪杰斯特拉(Dijkstra)提出的一个按路径长度递增的次序产生最短路径的算法。这个算法是迪杰斯特拉教授在他26岁陪未婚妻逛街时想出来的，数学家在逛街疲惫休息时想出了如何提高逛街效率的方法，查找逛街的最短路径。对于权值全为正的图，Dijkstra算法是解决单源最短路径的常用算法。凭借这一算法，迪杰斯特拉教授获得了图灵奖。 1. Dijkstra算法的思想 设G (V,E)是一幅带权有向图(无向可以转换为双向有向),设置两个顶点的集合S和TVS,集合S中存放已找到最短路径的顶点,集合T存放当前还未找到最短路径的顶点。初始状态时,集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入集合S中,集合S每加入一个新的顶点u,都要修改顶点v0到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。不断重复此过程,直到集合T的顶点全部加入S中为止。 Dijkstra算法的正确性可以用反证法加以证明。假设下一条最短路径的终点为x,那么,该路径必然或者是弧(v0,x),或者是中间只经过集合S中的顶点而到达顶点x的路径。因为假若此路径上除x之外有一个或一个以上的顶点不在集合S中,那么必然存在另外的终点不在S中而路径长度比此路径还短的路径,这与按路径长度递增的顺序产生最短路径的前提相矛盾,所以此假设不成立。 观看视频 2. Dijkstra算法的具体步骤 (1) 初始时,S只包含源点,即S{v},v的距离dist［v］为0。T包含除v外的其他顶点,T中顶点u距离dist［u］为边上的权值(有边G.vexnum;++w) /*更新当前最短路径*/ if (!final［w］&&(min+G.edges［v］［w］ using namespace std; #define inf 1<<29 #define MAXV 1005 int map［MAXV］［MAXV］; int n,m; void dijkstra(){ int i,j,min,v; int d［MAXV］; bool vis［MAXV］; for(i=1;i<=n;i++){ vis［i］=0; d［i］=map［1］［i］; } for(i=1;i<=n;i++){ min=inf; for(j=1;j<=n;j++) if(!vis［j］ && d［j］map［v］［j］+d［v］) d［j］=map［v］［j］+d［v］; } printf("%d＼n",d［n］); } int main(){ int i,j,a,b,c; while(~scanf("%d%d",&m,&n)){ for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) map［i］［i］=0; else map［i］［j］=map［j］［i］=inf; for(i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); if(map［a］［b］>c) map［a］［b］=map［b］［a］=c; } dijkstra(); } return 0; } Dijkstra算法的核心是以起始点为中心向外层层扩展,直到扩展到终点为止。对于单源最短路径问题,一般有以下两种经典解法。 （1) 对于有权值为负的图,采用BellmanFord算法。 （2) 对于权值全为正的图,常采用Dijkstra算法。 BellmanFord算法将在5.5.3节介绍。 观看视频 5.5.3具有负值边的图 如果图具有负值边,那么Dijkstra算法是行不通的。问题在于一旦一个顶点u被声明是已知的,就可能从某个另外的未知顶点v有一条回到u的负的路径。 一个诱人的解决方案是将一个常数Δ加到每条边上,从而除去负值边,再计算新图的最短路径,然后把结果用到原来的图上。这种方案不可能直接实现,因为那些须有许多条边的路径变得比那些具有很少边的路径权重更重了。另一个思路是把带权和无权的算法结合起来将会解决这个问题,但是要付出运行时间激烈增长的代价。下面主要介绍一个常用的能解决该问题的BellmanFord算法。 BellmanFord算法是由美国数学家理查德·贝尔曼(Richard Bellman,动态规划的提出者)和小莱斯特·福特(Lester Ford)发明的。 1. BellmanFord算法思想 BellmanFord算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图G (V,E),其源点为s,加权函数w是边集E的映射。对图G运行BellmanFord算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到图G的任意顶点v的最短路径Distant［v］,否则无解。 2. BellmanFord算法流程 (1) 初始化： 数组Distant［i］记录从源点s到顶点i的路径长度，初始化数组Distant［i］，源点s的Distant［s］为0，除源点外其他顶点i的Distant［i］为∞。 (2) 迭代求解： 反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离(运行|v|1次),即对于每条边e(u,v),如果Distant［u］w(u,v) Distant［v］,则令Distant［v］ Distant［u］w(u, v)。w(u, v)为边e(u,v)的权值。 若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环; 否则执行下次循环。 (3) 检验负权回路： 判断边集E中的每条边的两个端点是否收敛,即对于每条边e(u, v),如果存在Distant［u］ w(u, v) Distant［v］的边,且权值之和小于0,则图中存在负环路,该图无法求出单源最短路径。如果存在不收敛的顶点,则算法返回false,表明问题无解; 否则算法返回true,并且从源点可达的顶点v的最短距离保存在Distant［v］中。 算法描述如下。 Bellman-Ford(G,w,s)： boolean //图G,边集函数w,s为源点 for each vertex v ∈ V(G) do 　　//初始化,1阶段 d［v］ ←+∞ d［s］ ←0; 　　//1阶段结束 for i=1 to |v|-1 do 　　//2阶段开始,双重循环 for each edge(u,v)∈E(G) do 　　//边集数组要用到,穷举每条边 If d［v］>d［u］+ w(u,v) then //松弛判断 d［v］=d［u］+w(u,v) 　　//松弛操作,2阶段结束 for each edge(u,v)∈E(G) do If d［v］>d［u］+ w(u,v) then return false return true BellmanFord算法寻找单源最短路径的时间复杂度为O(V·E)。 3. BellmanFord算法描述性证明 首先,图的任意一条最短路径既不能包含负权回路,也不会包含正权回路,因此它最多包含|v|1条边。 其次,从源点s可达的所有顶点如果存在最短路径,则这些最短路径构成一个以s为根的最短路径树。BellmanFord算法的迭代松弛操作,实际上就是按顶点距离s的层次,逐层生成这棵最短路径树的过程。 在对每条边进行第1遍松弛时,生成了从s出发,层次至多为1的那些树枝。也就是说,找到了与s至多有1条边相连的那些顶点的最短路径; 在对每条边进行第2遍松弛时,生成了第2层次的树枝,就是说找到了经过2条边相连的那些顶点的最短路径……因为最短路径最多只包含|v|1条边,所以,只需要循环|v|1次。 每实施一次松弛操作,最短路径树上就会有一层顶点达到其最短距离,此后这层顶点的最短距离值就会一直保持不变,不再受后续松弛操作的影响。 如果没有负权回路,由于最短路径树的高度最多只能是|v|1,因此最多经过|v|1遍松弛操作后,所有从s可达的顶点必将求出最短距离。如果d［v］仍保持∞,则表明从s到v不可达。如果有负权回路,第|v|1遍松弛操作仍会成功,但负权回路上的顶点不会收敛。 4. BellmanFord算法过程演示 BellmanFord算法是最简单的算法,就是从开始结点开始循环每一条边,对它进行松弛操作,最后得到的路径就是最短路径。执行过程如图5.38所示。 图5.38BellmanFord算法的执行过程 在图5.38中,源点是顶点s。d值被标记在顶点内,阴影覆盖的边指示了前驱值。图5.38(a)示出了对边进行第一趟操作前的情况。图5.38(b)~图5.38(e)示出了每一趟连续对边操作后的情况。图5.38(e)中d的值是最终结果。BellmanFord算法在本例中返回的是True。 5. BellmanFord算法参考代码 算法5.26 #include #include using namespace std; #define MAX 0x3f3f3f3f #define N 1010 int nodenum, edgenum, original; //点、边、起点 typedef struct Edge 　　//边 {int u, v; int cost; }Edge; Edge edge［N］; int dis［N］, pre［N］; bool Bellman_Ford() {for(int i = 1; i<= nodenum; ++i) 　　//初始化 dis［i］ = (i == original ? 0 : MAX); for(int i = 1; i<= nodenum - 1; ++i) for(int j = 1; j<= edgenum; ++j) if(dis［edge［j］.v］>dis［edge［j］.u］ + edge［j］.cost)//松弛(顺序一定不能反) {dis［edge［j］.v］ = dis［edge［j］.u］ + edge［j］.cost; pre［edge［j］.v］ = edge［j］.u; } bool flag = 1; 　　//判断是否含有负权回路 for(int i = 1; i<= edgenum; ++i) if(dis［edge［i］.v］>dis［edge［i］.u］ + edge［i］.cost) {flag = 0; break; } return flag; } void print_path(int root) 　　//打印最短路的路径(反向) {while(root != pre［root］) 　　//前驱 {printf("%d-->", root); root = pre［root］; } if(root == pre［root］) printf("%d＼n", root); } int main() {scanf("%d%d%d", &nodenum, &edgenum, &original); pre［original］ = original; for(int i = 1; i<= edgenum; ++i) {scanf("%d%d%d", &edge［i］.u, &edge［i］.v, &edge［i］.cost); } if(Bellman_Ford()) for(int i = 1; i<= nodenum; ++i) 　　//每个点的最短路 { printf("%d＼n", dis［i］); printf("Path:"); print_path(i); } else printf("have negative circle＼n"); return 0; } 建议读者利用BellmanFord算法重解例5.5。 观看视频 5.5.4所有点对的最短路径 Dijkstra算法是求单源最短路径的,如果求图中所有点对的最短路径，则有以下两种解法。 (1) 以图中的每个顶点作为源点,分别调用Dijkstra算法,时间复杂度为O(n3)。 (2) Floyd算法更简洁,但算法时间复杂度仍为O(n3)。 本节主要介绍Floyd提出的一个算法。 Floyd算法是另一种经典的最短路径算法,不同的是Dijkstra算法仅计算了从一个起点出发的最短路径,而Floyd算法可以计算全部结点到其他结点的最短路径。Floyd算法的基本思想也是松弛。这是一个动态规划的经典例子,在求解各点到其他点的最短路径的过程中往往会有很多的重叠问题,通过表D［］［］将这些问题保存下来,避免了重复的计算。 1. Floyd算法基本思想 Floyd算法仍从图的带权邻接矩阵cost出发,假设求从顶点vi到vj的最短路径。如果从vi到vj有弧,则从vi到vj存在一条长度为edges［i］［j］的路径,该路径不一定是最短路径,尚需进行n次试探。首先考虑路径(vi,v0,vj)是否存在(即判别弧(vi,v0)和(v0,vj)是否存在)。如果存在,则比较(vi,vj)和(vi,v0,vj)的路径长度，取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点v1,也就是说,如果(vi,…,v1)和(v1,…,vj)分别是当前找到的中间顶点的序号不大于1的最短路径,那么(vi,…,v1,…,vj)就有可能是从vi到vj的中间顶点序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较,从中选出中间顶点序号不大于1的最短路径,再增加一个顶点v2,继续进行试探，以此类推。在一般情况下,若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k的最短路径,则将(vi,…,vk,…,vj)和已经得到的从vi到vj且中间顶点序号不大于k1的最短路径相比较,其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样,在经过n次比较后,最后求得的必是从vi到vj的最短路径。按此方法,可以同时求得各对顶点间的最短路径。 2. Floyd算法的基本步骤 现定义一个n阶方阵序列： D(1),D(0),D(1),…,D(k),D(n1)。 初始化： D(1)cost,D(1)［i］［j］edges［i］［j］,表示初始的从i到j的中间不经过其他中间点的最短路径。 迭代： 设D(k1)已求出,如何得到D(k)(0≤k≤n1)是该算法的关键,也是该算法中动态规划的主要思想,由Floyd算法基本思想可得： D(k)［i］［j］Min{D(k1)［i］［j］, D(k1)［i］［k］D(k1)［k］［j］}，0≤k≤n1 从上述计算公式可见,D(1)［i］［j］是从vi到vj的中间顶点的序号不大于1的最短路径的长度; D(k)［i］［j］是从vi到vj的中间顶点的个数不大于k的最短路径的长度; D(n1)［i］［j］就是从vi到vj的最短路径的长度。 3. Floyd算法实现 由上述动态规划方程可知,可以用3个for循环来实现Floyd算法,需要注意的是for循环的嵌套顺序： for(int k=0; k #include #include #include #include using namespace std; const int maxn=1000; const int inf=10000000; int map［maxn］［maxn］; void floyd(int n){ for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) map［i］［j］=min(map［i］［j］,map［i］［k］+map［k］［j］); } int main(){ int n; while(~scanf("%d",&n),n){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) if(i==j) map［i］［j］=0; else map［i］［j］=inf; //初始化 int m; scanf("%d",&m); while(m--){ int x,c; scanf("%d%d",&x,&c); if(c typedef struct { elemtype v1; elemtype v2; int cost; } EdgeType; EdgeType edges［MAXEDGE］; 在结构数组edges中,每个分量edges［i］代表网中的一条边,其中edges［i］.v1和edges［i］.v2表示该边的两个顶点,edges［i］.cost表示这条边的权值。为了方便选取当前权值最小的边,事先把数组edges中的各元素按照其cost域值由小到大的顺序排列。在对连通分量合并时,采用集合的合并方法。对于有n个顶点的网,设置一个数组father［n］,其初值为father［i］1(i0,1,…,n1),表示各顶点在不同的连通分量上,然后,依次取出edges数组中的每条边的两个顶点,查找它们所属的连通分量,假设vf1和vf2为两顶点所在的树的根结点在father数组中的序号,若vf1不等于vf2,表明这条边的两个顶点不属于同一分量,则将这条边作为最小生成树的边输出,并合并它们所属的两个连通分量。 下面用C语言实现Kruskal算法,其中函数Find的作用是寻找图中顶点所在树的根结点在数组father中的序号。需说明的是,在程序中将顶点的数据类型定义成整型,而在实际应用中,可依据实际需要来设定。 算法5.30 typedef int elemtype; typedef struct { elemtype v1; elemtype v2; int cost; }EdgeType; void Kruskal(EdgeType edges［ ］,int n) /*用Kruskal算法构造有n个顶点的图edges的最小生成树*/ {int father［MAXEDGE］; int i,j,vf1,vf2; for (i=0;i=0) t=father［t］; return(t); } 在Kruskal算法中,第二个while循环是影响时间效率的主要操作,其循环次数最多为MAXEDGE,其内部调用的Find函数的内部循环次数最多为n,所以Kruskal算法的时间复杂度为O(n·MAXEDGE)。 5.6.3最小生成树算法应用 例5.7农业网(AgriNet)： 给出N个顶点及N个顶点间的距离,然后求一棵最小生成树。先输入顶点数N,然后一个N×N的数组,用来描述各个顶点之间的距离。 输入包含若干种情况,每种情况,第一行是农场数N (3≤N≤100),接着是N×N的邻接距离矩阵,逻辑上说有N行以空格分开的N个整数,物理上说,每行长度限制为80个字符,所以有些行会延续到其他行。要求对每个用例以整数形式输出连接整个农场需要的光纤最小长度。［POJ 1258］ 输入示例 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 输出示例 28 参考代码如下。 算法5.31 #include using namespace std; const int INFINITY = 9999999; const int MAXVEX = 102; int edge［MAXVEX］［MAXVEX］, lowcost［MAXVEX］; int vexNum; int myPrim(int start); int main() { while（scanf("%d",&vexNum)!=EOF) { for(int i = 1; i<= vexNum; i++) for(int j = 1; j<= vexNum; j++) scanf("%d", &edge［i］［j］); printf("%d＼n",myprim(1)); } return 0; } int myPrim(int start) { int nextVex, minEdge, sumPath = 0; for(int i = 1; i<= vexNum; i++) lowcost［i］ = edge［start］［i］; for(int i = 1; i0) && (lowcost［j］0)){ lowcost［j］ = edge［nextVex］［j］; } } } return sumPath; } 观看视频 5.7网络流问题 设给定边容量为Cv,w的有向图G (V,E)。这些容量可以代表通过一个管道的水的容量或在两个交叉路口之间马路上的交通流量。有两个顶点： 一个是s,称为源点(Source)； 另一个是t,称为汇点(Sink)。对于任意一条边(v,w),最多有“流”Cv,w个单位可以通过。在既不是源点s又不是汇点t的任一顶点v,总的进入的流必须等于总的发出的流。最大流问题就是确定从s到t可以通过的最大流量。例如,对于图5.44(a),最大流是5,如图5.44(b)所示。 图5.44一幅图和它的最大流 正如问题叙述中所要求的,没有边负载超过它的容量的流。源点s将5个单位的流分给a和b,顶点a有3个单位的流进入,它将这3个流分转给c和d。顶点d从a和b得到3个单位的流,并把它们结合起来发送到t。一个顶点在不违反边的容量以及保持流守恒(进入必须流出)的前提下,可以按任何方式结合和发送流。 5.7.1网络流的最大流问题 本节开始讨论解决最大流问题的FordFulkerson方法,该方法也称作“扩充路径方法”,该方法是大量算法的基础,有多种实现方法(如EdmondsKarp算法、Dinic算法等)。FordFulkerson算法是一种迭代算法,首先对图中所有顶点对的流清零,此时的网络流大小也为0。在每次迭代中,通过寻找一条“增广路径”(Augument Path)来增加流的值。增广路径可以看作源点s到汇点t的一条路径,并且沿着这条路径可以增加更多的流。迭代直至无法再找到增广路径为止,此时必然从源点到汇点的所有路径中都至少有一条满边。 1. 一个简单的最大流问题 从图G开始并构造一幅流图f,f表示在算法的任意阶段已经达到的流。开始时f的所有边都没有流,希望当算法终止时f包含最大流。再构造一幅图Gf,称为残余图(Residual Graph),它表示对于每条边还能再添加上多少流。对于每一条边,可以从容量中减去当前的流而计算出残余的流。Gf的边叫作残余边(Residual Edge)。 所谓增广通路(Augmenting Path)，指图Gf中从s到t的一条路径,而且在每个阶段,都需要找到这条路径。这条路径上的最小值边就是可以添加到路径每条边上的流量,这可以通过调整f和重新计算Gf来实现。当发现在Gf中没有从s到t的路径时算法终止。这个算法是不确定的,因为从s到t的路径是任意选择的。显然,有些选择会比另外一些选择好,后面再处理这个问题。针对例子运行这个算法。要记着这个算法有一个小欠缺。G、f和Gf的初始配置如图5.45所示。 图5.45图、流图以及残余图的初始阶段 在残余图中有许多从s到t的路径。假设选择s，b，d，t,此时可以发送2个单位的流通过这条路径的每一边。采用如下约定： 一旦注满(使饱和)一条边,则这条边就要从残余图中除去。这样就得到图5.46。 图5.46沿s,b,d,t加入2个单位的流后的G、f、Gf 若选择路径s，a，c，t,该路径也容许2个单位的流通量。进行必要的调整后,得到图5.47中的图。 图5.47沿s,a,c,t加入2个单位的流后的G、f、Gf 唯一剩下可选择的路径是s,a,d,t,这条路径能够容纳一个单位的流通过。结果得到如图5.48所示的图。 图5.48沿s,a,d,t加入1个单位的流后的G、f、Gf——算法终止 由于t从s出发是不可达到的,因此算法到此终止。结果正好5个单位的流是最大值。为了看清问题的所在,设从初始图开始选择路径s,a,d,t，这条路径容纳3个单位的流,从表面上看这是个好选择。然而选择的结果却使得在残余图中不再有从s到t的任何路径,因此,该算法不能找到最优解。这是贪婪算法行不通的一个例子。图5.49指出了为什么算法会失败。 图5.49如果初始动作是沿s,a,d,t加入3个单位的流得到G、f、Gf ——算法终止但解不是最优的 为了使得算法有效,就需要让算法改变它的意向。为此,对于流图中具有流fv,w的每一边(v,w)将在残余图中添加一条容量为fv,w的边(w,v)。事实上,可以通过以相反的方向发回一个流而使算法改变它的意向。通过例子最能看清楚这个问题。从原始的图开始并选择增长通路s,a,d,t得到图5.50中的图。 图5.50使用正确的算法沿s,a,d,t加入3个单位的流后的图 注意,在残余图中有些边在a和d之间有两个方向。或者还有一个单位的流可以从a导向d,或者有高达3个单位的流导向相反的方向——可以撤销流。现在算法找到流为2的增长通路s,b,d,a,c,t。通过从d到a导入2个单位的流,算法从边(a,d)取走2个单位的流,因此本质上改变了它的意向。图5.51显示出新的图。 图5.51使用正确算法沿s,b,d,a,c,t加入2个单位的流后的图 在图5.51中没有增广通路,因此,算法终止。奇怪的是,可以证明,如果边的容量都是有理数,那么该算法总以最大流终止。证明多少有些困难,也超出了本书的范围。虽然例子正好是无环的,但这并不是算法有效工作所必需的。此处使用无环图只是为了简明。 2. FordFulkerson算法的正确性证明 利用最大流最小割定理可以证明FordFulkerson算法的正确性。 最大流最小割定理： 一个网中所有流中的最大值等于所有割中的最小容量。并且可以证明以下3个条件等价。 (1) f是流网络G的一个最大流。 (2) 残留网Gf不包含增广路径。 (3) G的某个割(S, T),满足f(S, T) c(S, T)。 证明如下。 (1) (反证法)假设f是G的最大流,但是Gf中包含增广路径p。显然此时沿着增广路径可以继续增大网络的流,则f不是G的最大流,与条件矛盾。 (2) 假设Gf中不包含增广路径,即Gf中不包含从s到t的路径。定义： S {v∈V： Gf中包含s到v的路径} 令T VS,由于Gf中不存在从s到t的路径,因此tS,所以得到G的一个割(S, T)。对每对顶点u∈S,v∈T,必须满足f(u, v) c(u, v),否则边(u, v)就会存在于Gf的边集合中,那么v就应当属于S(而事实上是v∈T)。所以,f(S, T) c(S, T)。 (3) 网络的任何流的值都不大于任何一个割的容量,如果G的某个割(S, T),满足f(S, T)c(S, T),则说明割(S, T)的流达到了网络流的上确界,它必然是最大流。 FordFulkerson算法的迭代终止条件是残留网中不包含增广路径,根据上面的等价条件,此时得到的流就是网络的最大流。 3. FordFulkerson算法的实现 依据上面的讨论,下面给出FordFulkerson算法的伪代码。 算法5.32 Ford-Fulkerson(G, s, t) for each edge (u, v)∈E［G］ //初始化每条边的流量为0 {f［u, v］ = 0; f［v, u］ = 0; } //Gf←G //初始化剩余网络Gf为原网络G,这里不需要代码 while there exists a path p from s to t in the network Gf //网络中还存在增广路径,仍然进行迭代 {search a path p from network Gf //EdmondsKarp算法采用广度优先搜索算法,Dinic //算法采用深度优先搜索算法 cf (p)=Min{cf (u, v) | (u, v) is in p} //确定增广路径上的流增量Δf(p)= cf (p) for each edge (u, v) in p {f［u, v］ = f［u, v］ + cf (p) 　　//增加剩余网络中增广路径上每条边的流量 f［v, u］ = - f［u, v］ //显然该路径上反方向上的容量为负 cf ［u, v］ = c［u, v］ - f［u, v］ //计算剩余网络Gf中的每条边的容量 cf ［v, u］ = c［v, u］ - f［v, u］ } } EdmondsKarp算法与FordFulkerson算法的主要区别在于： Karp算法采用广度优先搜索算法寻找一条从s到t最短增广路径; Dinic算法则在层次概念的基础上采用深度优先搜索算法寻找增广路径。 4. EdmondsKarp算法参考模板 为便于读者尽快掌握网络流算法,下面给出一个EdmondsKarp算法的参考模板。 设有n个顶点、m条有向边的网图G,源点为1,汇点为n。每条有向边上的容量和流量分别用c［I,j］和f［I,j］表示,则EdmondsKarp参考代码如下。 算法5.33 #include #include using namespace std; const int maxn=205; const int inf=0x7fffffff; int r［maxn］［maxn］; //残留网络,初始化为原图 bool visit［maxn］; int pre［maxn］; int m,n; bool bfs(int s,int t) 　　//寻找一条从s到t的增广路径,若找到返回true {int p; queueq; memset(pre,-1,sizeof(pre)); memset(visit,false,sizeof(visit)); pre［s］=s; visit［s］=true; q.push(s); while(!q.empty()) {p=q.front(); q.pop(); for(int i=1;i<=n;i++) {if(r［p］［i］>0&&!visit［i］) { pre［i］=p; visit［i］=true; if(i==t) return true; q.push(i); } } } return false; } int EdmondsKarp(int s,int t) { int flow=0,d,i; while(bfs(s,t)) {d=inf; for(i=t;i!=s;i=pre［i］) d=d using namespace std; int c［VMAX］［VMAX］; 　　//容量 int n, m; 　　//分别表示图的边数和顶点数 int Edmonds_Karp(int s, int t) //输入源点和汇点 {int p, q, queue［VMAX］, u, v, pre［VMAX］, flow=0, aug; while(true) {memset(pre,-1,sizeof(pre)); 　　//记录双亲结点 for(queue［p=q=0］=s; p<=q; p++ ) 　　//广度优先搜索 {u= queue［p］; for(v=0; v0 && pre［v］<0) pre［v］=u, queue［++q］=v; if(pre［t］>=0) break; } if(pre［t］<0)break; 　　//不存在增广路径 aug=0x7fffffff; 　　//记录最小残留容量 for(u=pre［v=t］; v!=s; v=u,u=pre［u］) if(c［u］［v］ 0. 输出 The output has to contain a single floating point number. 输入示例输出示例 0 0 8 08.24621 2 0 4 5 8 4 5 参考代码如下。 算法5.35 #include #include #include #include #include using namespace std; int cap［1000］［1000］; int flow［1000］［1000］; int a［1000］; int f; int p［1000］; const int inf = 0x7fffffff; void Edmonds_karp(int N, int M) {dequeq; int t, u, v, x; memset(flow, 0, sizeof(flow)); memset(p, 0, sizeof(p)); f = 0; for (; ; ) {memset(a, 0, sizeof(a)); a［1］ = inf; q.push_back(1); while (!q.empty()) {u = q.front(); q.pop_front(); for(v = 1; v<= M; v++) if (!a［v］ && cap［u］［v］>flow［u］［v］) {p［v］ = u; q.push_back(v); a［v］ = min(a［u］, cap［u］［v］ - flow［u］［v］); } } if (a［M］ == 0) break; for (u = M; u != 1; u = p［u］) {flow［u］［p［u］］ -= a［M］; flow［p［u］］［u］ += a［M］; } f += a［M］; } } int main() {int N, M, i, j, a, b, c; while (scanf("%d%d", &N, &M) != EOF) { memset(cap, 0, sizeof(cap)); f = 0; for (i = 0; i