数据结构图的算法的毕业论文

图图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。1图的基本概念和存储结构11图的定义图（GRAPH）是由非空的顶点集合V与描述顶点之间关系边（或者弧）的集合E组成，其形式化定义为GV,E如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“”表示。例如，顶点偶对VI,VJ表示顶点VI和顶点VJ相连的边，并且VI,VJ与VJ,VI表示同一条边。如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“”表示。例如，顶点偶对表示从顶点VI指向顶点VJ的一条有向边；其中，顶点VI称为有向边的起点，顶点VJ称为有向边的终点。有向边也称为弧；对弧来说，VI为弧的起点，称为弧尾；VJ为弧的终点，称为弧头。图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知一个图的信息包括两个部分图中顶点的信息以及描述顶点之间的关系边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用C语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为VV0,V1,VN1。下面介绍几种常用的图的存储结构。12邻接矩阵所谓邻接矩阵存储结构，就是用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。假定图GV,E有N个顶点，即VV0,V1,VN1，则表示G中各顶点相邻关系需用一个NN的矩阵，且矩阵元素为AIJ若G是带权图（网），则邻接矩阵可定义为AIJ其中，WIJ表示VI,VJ或上的权值；则为计算机上所允许的大于所有边上权值的数值。无向图的邻接矩阵表示如图76所示。图76无向图及邻接矩阵表示有向图的邻接矩阵表示如图77所示。图77有向图及邻接矩阵表示带权图的邻接矩阵表示如图78所示。1若VI,VJ或是E中的边0若VI,VJ或不是E中的边WIJ若VI,VJ或是E中的边0或若VI,VJ或不是E中的边图78带权图及邻接矩阵表示从图的邻接矩阵可以看出以下特点（1）无向图（包括带权图）的邻接矩阵一定是一个按对角线对称的对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2）对于无向图，邻接矩阵的第I行或第I列的非零元素（或非元素）个数正好是第I个顶点的度DVI。（3）对有向图，邻接矩阵的第I行非零元素（或非元素）的个数正好是第I个顶点的出度ODVI，第I列非零元素（或非元素）的个数正好是第I个顶点的入度IDVI。（4）用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中具体有多少条边，则必须按行、按列对每一个元素进行查找后方能确定，因此花费的时间代价较大，这也是用邻接矩阵存储图的局限性。在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的邻接矩阵之外，还需要用一个一维数组存储顶点信息。这样，一个图在顺序存储结构下的类型定义为；TYPEDEFSTRUCTCHARVERTEXMAXNUM/顶点为字符型且顶点表的长度小于MAXNUM/INTEDGESMAXNUMMAXNUM/边为整型且EDGES为邻接矩阵/MGRAPH/MGRAPH为采用邻接矩阵存储的图类型/建立一个无向图的邻接矩阵程序如下INCLUDEINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTCHARVERTEXMAXSIZE/顶点为字符型且顶点表的长度小于MAXSIZEINTEDGESMAXSIZEMAXSIZE/边为整型且EDGES为邻接矩阵MGRAPH/MGRAPH为采用邻接矩阵存储的图类型VOIDCREATMGRAPHMGRAPHG,INTE,INTN/建立无向图的邻接矩阵GEGDES，N为顶点个数，E为边数INTI,J,KPRINTF“INPUTDATAOFVERTEXS0N1N“FORI0IVERTEXII/读入顶点信息FORI0IEDGESIJ0/初始化邻接矩阵FORK1KEDGESIJ1GEDGESJI1VOIDMAININTI,J,N,EMGRAPHG/建立指向采用邻接矩阵存储图类型指针GMGRAPHMALLOCSIZEOFMGRAPH/生成采用邻接矩阵存储图类型的存储空间PRINTF“INPUTSIZEOFMGRAPH“/输入邻接矩阵的大小SCANF“D“,PRINTF“INPUTNUMBEROFEDGE“/输入邻接矩阵的边数SCANF“D“,CREATMGRAPHG,E,N/生成存储图的邻接矩阵PRINTF“OUTPUTMGRAPHN“/输出存储图的邻接矩阵FORI0IEDGESIJPRINTF“N“【说明】无向图的邻接矩阵表示如图151所示。图151无向图及邻接矩阵表示对图151所示的无向图，程序执行如下输入INPUTSIZEOFMGRAPH4INPUTNUMBEROFEDGE4INPUTDATAOFVERTEXS0N1INPUTEDGEOFI,J0,1INPUTEDGEOFI,J0,3INPUTEDGEOFI,J1,3INPUTEDGEOFI,J1,2输出OUTPUTMGRAPH0101101101001100PRESSANYKEYTOCONTINUE0101A101101001100V0V3V1V213邻接表邻接表是图的一种顺序存储与链式存储相结合的存储方法。邻接表表示法类似于树的孩子表示法。也即，对于图G中的每个顶点VI，将所有邻接于VI的顶点VJ链成一个单链表，这个单链表就称为顶点VI的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表。用邻接表表示的图有两种结构，如图79所示。图79邻接表表示的结点结构一种是用一维数组表示的顶点表的结点（即数组元素）结构，它由顶点域（VERTEX）和指向该顶点第一条邻接边的指针域（FIRSTEDGE）（也即，这个指针指向该顶点的邻接表）所构成。另一种是邻接表结点（边结点），它由邻接点域ADJVEX和指向下一条邻接边的指针域（NEXT）所构成。对带权图（网）的邻接表结点则需增加一个存储边上权值信息的这样一个域。因此，带权图的邻接表结点结构如图710所示。图710带权图（网）的邻接表结点结构图711给出了图76所示的无向图所对应的邻接表表示。图711无向图的邻接表表示邻接表表示下的类型定义为TYPEDEFSTRUCTNODE/邻接表结点/INTADJVEX/邻接点域/STRUCTNODENEXT/指向下一个邻接边结点的指针域/EDGENODE/邻接表结点类型/TYPEDEFSTRUCTVNODE/顶点表结点/INTVERTEX/顶点域/EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域/VERTEXNODE/顶点表结点类型/建立一个无向图的邻接表存储算法如下VOIDCREATADJLIST（VETEXNODEG,INTE,INTN）/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点/EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N”FORI0IADJEXJ/在顶点VI的邻接表中添加邻接点为J的结点/PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的/GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点/PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的/GIFIRSTEDGEP2图的遍历图的遍历是指从图中的任一顶点出发，按照事先确定的某种搜索方法依次对图中所有顶点进行访问且仅访问一次的过程。图的遍历要比树的遍历复杂得多，其复杂性主要表现在以下4个方面（1）在图结构中，没有象树根结点那样“自然”的首结点，即图中的任何一个顶点都可以作为第一个被访问的结点。（2）在非连通图中，从一个顶点出发只能访问它所在的连通分量上的所有顶点；因此，还需考虑如何选取下一个未被访问的顶点来继续访问图中其余的连通分量。（3）在图结构中如果有回路存在，则一个顶点被访问后有可能沿回路又回到该顶点。（4）在图结构中一个顶点可以和其它多个顶点相邻，当该顶点访问过后则存在如何从众多相邻顶点中选取下一个要访问的顶点问题。图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。图的遍历通常采用深度优先搜索（DEPTHFIRSTSEARCH,DFS）和广度优先搜索（BREADTHFIRSTSEARCH,BFS）两种方式，这两种方式对无向图和有向图的遍历都适用。21深度优先搜索深度优先搜索对图的遍历类似于树的先根遍历，是树的先根遍历的一种推广；也即，搜索顶点的次序是沿着一条路径尽量向纵深发展。深度优先搜索的基本思想是假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点V出发即先访问V，然后依次从V的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和V有路径相通的顶点都被访问过；若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。我们以图718的无向图为例进行图的深度优先搜索。假定从顶点V0出发，在访问了顶点V0后选择邻接点V1作为下一个访问的顶点；由于V1未曾访问过，则访问V1并继续由V1开始搜索下一个邻接点V3作为访问顶点；V3同样没有访问过，则访问V3并继续搜索下一个邻接点V6；V6也未访问过，则访问V6再继续搜索下一个邻接点V4；V4未曾访问过，则访问V4并继续搜索下一个邻接点V1，此时由于V1已被访问过则回退至V4继续搜索V4的下一个邻接点；由于V4已无未被访问过的邻接点，则继续回退到V6再搜索V6的未被访问邻接点；这种回退一直持续到V0，此时可搜索到V0的未被访问邻接点V2，即访问V2并继续搜索下一个邻接点V5；由于V5未被访问，则访问V5并继续搜索V5的邻接点；因V5已无未被访问过的邻接点故回退至V2，继续搜索V2的未被访问邻接点，但V2已无未被访问过的邻接点，则回退至V0，而V0也无未被访问的邻接点。由于V0为搜索图时的出发结点，故到此搜索结束。由此得到深度优先搜索遍历图的结点序列为V0V1V3V6V4V2V5图718无向图深度优先搜索示意显然，深度优先搜索遍历图的过程是一个递归过程，我们可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿着某条回路回到该顶点这种重复访问的情况出现，就必须在图的遍历过程中对每一个访问过的顶点进行标识，这样才可以避免一个顶点被重复访问的情况出现。所以，我们在遍历算法中对N个顶点的图设置了一个长度为N的访问标志数组VISITEDN，每个数组元素被初始化0，一旦某个顶点I被访问则相应的VISITEDI就置为1来做为访问过的标志。对以邻接表为存储结构的图（可为非连通图）进行深度优先搜索的程序如下INCLUDEINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTNODE/邻接表结点INTADJVEX/邻接点域STRUCTNODENEXT/指向下一个邻接边结点的指针域EDGENODE/邻接表结点类型TYPEDEFSTRUCTVNODE/顶点表结点INTVERTEX/顶点域EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域VERTEXNODE/顶点表结点类型VOIDCREATADJLISTVERTEXNODEG,INTE,INTN/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N“FORI0IADJVEXJ/在顶点VI的邻接表中添加邻接点为J的结点PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的GJFIRSTEDGEPINTVISITEDMAXSIZE/MAXSIZE为大于或等于无向图顶点个数的常量VOIDDFSVERTEXNODEG,INTIEDGENODEPPRINTF“4D“,GIVERTEX/输出顶点I信息，即访问顶点IVISITEDI1/置顶点I为访问过标志PGIFIRSTEDGE/根据顶点I的指针FIRSTEDGE查找其邻接表的第一个邻接边结点WHILEPNULL/当邻接边结点不为空时IFVISITEDPADJVEX/如果邻接的这个边结点未被访问过DFSG,PADJVEX/对这个边结点进行深度优先搜索PPNEXT/查找顶点I的下一个邻接边结点VOIDDFSTRAVERSEVERTEXNODEG,INTN/深度优先搜索遍历以邻接表存储的图，其中G为顶点表，N为顶点个数INTIFORI0IINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTNODE1/邻接表结点INTADJVEX/邻接点域STRUCTNODE1NEXT/指向下一个邻接边结点的指针域EDGENODE/邻接表结点类型TYPEDEFSTRUCTVNODE/顶点表结点INTVERTEX/顶点域EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域VERTEXNODE/顶点表结点类型VOIDCREATADJLISTVERTEXNODEG,INTE,INTN/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N“FORI0IADJVEXJ/在顶点VI的邻接表中添加邻接点为J的结点PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的GJFIRSTEDGEPTYPEDEFSTRUCTNODEINTDATASTRUCTNODENEXTQNODE/链队列结点的类型TYPEDEFSTRUCTQNODEFRONT,REAR/将头、尾指针纳入到一个结构体的链队列LQUEUEVOIDINIT_LQUEUELQUEUEQ/创建一个带头结点的空队列QNODEPQLQUEUEMALLOCSIZEOFLQUEUE/申请带头、尾指针的结点PQNODEMALLOCSIZEOFQNODE/申请链队列的头结点PNEXTNULL/头结点的NEXT指针置为空QFRONTP/队头指针指向头结点QREARP/队尾指针指向头结点INTEMPTY_LQUEUELQUEUEQ/判队空IFQFRONTQREAR/队为空RETURN1ELSERETURN0VOIDIN_LQUEUELQUEUEQ,INTX/入队QNODEPPQNODEMALLOCSIZEOFQNODE/申请新链队列结点PDATAXPNEXTNULL/新结点作为队尾结点时其NEXT域为空QREARNEXTP/将新结点P链到原队尾结点之后QREARP/使队尾指针指向新的队尾结点PVOIDOUT_LQUEUELQUEUEQ,INTX/出队QNODEPIFEMPTY_LQUEUEQPRINTF“QUEUEISEMPTYN“/队空，出队失败ELSEPQFRONTNEXT/指针P指向链队列第一个数据结点（即队头结点）QFRONTNEXTPNEXT/头结点的NEXT指针指向链队列第二个数据结点（即删除第一个数据结点）XPDATA/将删除的队头结点数据经由X返回FREEPIFQFRONTNEXTNULL/出队后队为空，则置为空队列QREARQFRONTINTVISITEDMAXSIZE/MAXSIZE为大于或等于无向图顶点个数的常量VOIDBFSVERTEXNODEG,LQUEUEQ,INTI/广度优先搜索遍历邻接表存储的图，G为顶点表，Q为队指针，I为第I个顶点INTJ,XEDGENODEPPRINTF“4D“,GIVERTEX/输出顶点I信息，即访问顶点IVISITEDI1/置顶点I为访问过标志IN_LQUEUEQ,I/顶点I入队QWHILEEMPTY_LQUEUEQ/当队Q非空时OUT_LQUEUEQ,X/队头顶点出队并送J（暂记为顶点J）PGJFIRSTEDGE/根据顶点J的表头指针查找其邻接表的第一个邻接边结点WHILEPNULLIFVISITEDPADJVEX/如果邻接的这个边结点未被访问过PRINTF“4D“,GPADJVEXVERTEX/输出这个邻接边结点的顶点信息VISITEDPADJVEX1/置该邻接边结点为访问过标志IN_LQUEUEQ,PADJVEX/将该邻接边结点送入队QPPNEXT/在顶点J的邻接表中查找J的下一个邻接边结点VOIDMAININTE,NVERTEXNODEGMAXSIZE/定义顶点表结点类型数组GLQUEUEQPRINTF“INPUTNUMBEROFNODEN“/输入图中结点个数SCANF“D“,PRINTF“INPUTNUMBEROFEDGEN“/输入图中边的个数SCANF“D“,PRINTF“MAKEADJLISTN“CREATADJLISTG,E,N/建立无向图的邻接表INIT_LQUEUE/队列Q初始化PRINTF“BFSTRAVERSEN“BFSG,Q,0/广度优先遍历以邻接表存储的无向图PRINTF“N“【说明】对图151所示的无向图，程序执行如下输入INPUTNUMBEROFNODE4INPUTNUMBEROFEDGE4MAKEADJLISTINPUTDATEOFVETEX0N1INPUTEDGEOFI,J0,1INPUTEDGEOFI,J0,3INPUTEDGEOFI,J1,3INPUTEDGEOFI,J1,2输出BFSTRAVERSE0312PRESSANYKEYTOCONTINUE23图的连通性问题判断一个图的连通性是图的应用问题，我们可以利用图的遍历算法来求解这一问题。1无向图的连通性在对无向图进行遍历时，对连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点；对于非连通图，则需要由不连通的多个顶点开始进行搜索，且每一次从一个新的顶点出发进行搜索过程中得到的顶点访问序列，就是包含该出发顶点的这个连通分量中的顶点集。因此，要想判断一个无向图是否为连通图，或者有几个连通分量，则可增加一个计数变量COUNT并设其初值为0，在深度优先搜索算法DFSTRAVERSE函数里的第二个FOR循环中，每调用一次DFS就给COUNT增1；这样当算法执行结束时的COUNT值即为连通分量的个数。无向图连通分量的计算程序如下INCLUDEINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTNODE1/邻接表结点INTADJVEX/邻接点域STRUCTNODE1NEXT/指向下一个邻接边结点的指针域EDGENODE/邻接表结点类型TYPEDEFSTRUCTVNODE/顶点表结点INTVERTEX/顶点域EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域VERTEXNODE/顶点表结点类型VOIDCREATADJLISTVERTEXNODEG,INTE,INTN/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N“FORI0IADJVEXJ/在顶点VI的邻接表中添加邻接点为J的结点PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的GJFIRSTEDGEPINTVISITEDMAXSIZE/MAXSIZE为大于或等于无向图顶点个数的常量VOIDDFSVERTEXNODEG,INTI/图的深度优先遍历EDGENODEPPRINTF“4D“,GIVERTEX/输出顶点I信息，即访问顶点IVISITEDI1/置顶点I为访问过标志PGIFIRSTEDGE/根据顶点I的指针FIRSTEDGE查找其邻接表的第一个邻接边结点WHILEPNULL/当邻接边结点不为空时IFVISITEDPADJVEX/如果邻接的这个边结点未被访问过DFSG,PADJVEX/对这个边结点进行深度优先搜索PPNEXT/查找顶点I的下一个邻接边结点INTCOUNT0/连通分量计数COUNT初值为0VOIDCONNECTEDGEVERTEXNODEG,INTN/求图的连通分量/深度优先搜索遍历以邻接表存储的图，其中G为顶点表，N为顶点个数INTIFORI0IADJVEX时，I是刚访问过顶点VI的序号，而PADJVEX是VI未被访问过且正准备访问的邻接边结点序号。所以，只要在DFS算法中的IF语句里，在递归调用DFSG,PADJVEX语句之前将边“I,PADJVEX”输出即可。同样也可在BFS算法中插入输出边的语句即可求得广度优先生成树算法。深度优先生成树程序如下INCLUDEINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTNODE/邻接表结点INTADJVEX/邻接点域STRUCTNODENEXT/指向下一个邻接边结点的指针域EDGENODE/邻接表结点类型TYPEDEFSTRUCTVNODE/顶点表结点INTVERTEX/顶点域EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域VERTEXNODE/顶点表结点类型VOIDCREATADJLISTVERTEXNODEG,INTE,INTN/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N“FORI0IADJVEXJ/在顶点VI的邻接表中添加邻接点为J的结点PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的GJFIRSTEDGEPINTVISITEDMAXSIZE/MAXSIZE为大于或等于无向图顶点个数的常量VOIDDFSTREEVERTEXNODEG,INTI/图的深度优先遍历EDGENODEPVISITEDI1/置顶点I为访问过标志PGIFIRSTEDGE/根据顶点I的指针FIRSTEDGE查找其邻接表的第一个邻接边结点WHILEPNULL/当邻接边结点不为空时IFVISITEDPADJVEX/如果邻接的这个边结点未被访问过PRINTF“D,D,“,I,PADJVEX/输出生成树中的一条边DFSTREEG,PADJVEX/对这个边结点进行深度优先搜索PPNEXT/查找顶点I的下一个邻接边结点VOIDDFSTRAVERSEVERTEXNODEG,INTN/生成深度优先生成树/深度优先搜索遍历以邻接表存储的图，其中G为顶点表，N为顶点个数INTIFORI0IINCLUDEDEFINEMAXSIZE30TYPEDEFSTRUCTINTDATAMAXSIZE/队中元素存储空间/INTREAR,FRONT/队尾和队头指针/SEQUEUEVOIDINT_SEQUEUESEQUEUEQQSEQUEUEMALLOCSIZEOFSEQUEUEQFRONT0QREAR0INTEMPTY_SEQUEUESEQUEUEQ/判队空IFQFRONTQREARRETURN1/队空ELSERETURN0/队不空VOIDIN_SEQUEUESEQUEUEQ,INTX/入队IFQREAR1MAXSIZEQFRONTPRINTF“QUEUEISFULLN“/队满，入队失败ELSEQREARQREAR1MAXSIZE/队尾指针加1QDATAQREARX/将元素X入队VOIDOUT_SEQUEUESEQUEUEQ,INTX/出队IFQFRONTQREARPRINTF“QUEUEISEMPTY“/队空，出队失败ELSEQFRONTQFRONT1MAXSIZE/队头指针加1XQDATAQFRONT/队头元素出队并由X返回队头元素值TYPEDEFSTRUCTNODE/邻接表结点INTADJVEX/邻接点域STRUCTNODENEXT/指向下一个邻接边结点的指针域EDGENODE/邻接表结点类型TYPEDEFSTRUCTVNODE/顶点表结点INTVERTEX/顶点域EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域VERTEXNODE/顶点表结点类型VOIDCREATADJLISTVERTEXNODEG,INTE,INTN/建立无向图的邻接表，N为顶点数，E为边数，G存储N个顶点表结点EDGENODEPINTI,J,KPRINTF“INPUTDATEOFVETEX0N1N“FORI0IADJVEXJ/在顶点VI的邻接表中添加邻接点为J的结点PNEXTGIFIRSTEDGE/插入是在邻接表表头进行的GIFIRSTEDGEPPEDGENODEMALLOCSIZEOFEDGENODEPADJVEXI/在顶点VJ的邻接表中添加邻接点为I的结点PNEXTGJFIRSTEDGE/插入是在邻接表表头进行的GJFIRSTEDGEPINTVISITEDMAXSIZE/MAXSIZE为大于或等于无向图顶点个数的常量VOIDBFSTREEVERTEXNODEG,INTI/生成广度优先生成树/广度优先搜索遍历邻接表存储的图，G为顶点表，Q为队指针，I为第I个顶点INTJ,XSEQUEUEQEDGENODEPVISITEDI1/置顶点I为访问过标志INT_SEQUEUEIN_SEQUEUEQ,I/顶点I入队QWHILEEMPTY_SEQUEUEQ/当队Q非空时OUT_SEQUEUEQ,X/队头顶点出队并送J（暂记为顶点J）PGJFIRSTEDGE/根据顶点J的表头指针查找其邻接表的第一个邻接边结点WHILEPNULLIFVISITEDPADJVEX/如果邻接的这个边结点未被访问过PRINTF“D,D,“,J,PADJVEX/输出生成树中的一条边VISITEDPADJVEX1/置该邻接边结点为访问过标志IN_SEQUEUEQ,PADJVEX/将该邻接边结点送入队QPPNEXT/在顶点J的邻接表中查找J的下一个邻接边结点VOIDMAININTE,NVERTEXNODEGMAXSIZE/定义顶点表结点类型数组GPRINTF“INPUTNUMBEROFNODEN“/输入图中结点个数SCANF“D“,PRINTF“INPUTNUMBEROFEDGEN“/输入图中边的个数SCANF“D“,PRINTF“MAKEADJLISTN“CREATADJLISTG,E,N/建立无向图的邻接表PRINTF“DFSTRAVERSEN“BFSTREEG,0/由顶点0开始生成广度优先生成树PRINTF“N“【说明】对图151所示的无向图，程序执行如下输入INPUTNUMBEROFNODE4INPUTNUMBEROFEDGE4MAKEADJLISTINPUTDATEOFVETEX0N1INPUTEDGEOFI,J0,1INPUTEDGEOFI,J0,3INPUTEDGEOFI,J1,3INPUTEDGEOFI,J1,2输出DFSTRAVERSE0,3,0,1,1,2,PRESSANYKEYTOCONTINUE32最小生成树与构造最小生成树的PRIM算法由于生成树的不唯一性，即从不同的顶点出发可能得到不同的生成树，对不同的存储结构从同一顶点出发也可能得到不同的生成树。在连通网中边是带权值的，则连通网的生成树各边也是带权值的，我们把生成树各边权值总和称为生成树的权；那么，对无向连通图构成的连通网，则它的所有生成树中必有一棵边的权值总和为最小的生成树，我们称这棵生成树为最小生成树。最小生成树有许多重要的应用，如以尽可能低的总造价建立N个城市间的通讯网络。我们可以用连通网来表示N个城市以及N个城市之间可能设置的通讯线路；其中网的顶点表示城市、边表示两城市之间的线路，边的权值表示该线路的造价。要想使总的造价最低，实际上就是寻找该网络的最小生成树。构造最小生成树必须解决好以下两个问题（1）尽可能选取权值小的边，但不能构成回路。（2）选取合适的N1条边将连通网的N个顶点连接起来。构造最小生成树的算法主要是利用最小生成树的一种简称为MST的性质设GV，E是一个连通网络，U是顶点集合V的一个真子集。若U,V是G的所有边中一个顶点在U即UU里，而另一个顶点不在U即VVU里且具有最小权值的一条边，则最小生成树必然包含边U,V。普里姆（PRIM）算法就是一种依据MST性质构造最小生成树的方法。假设GV，E为一连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为UU0（假设构造最小生成树时是从顶点U0出发），集合T的初值为T。PRIM算法的思想是在连通网中寻找一个顶点落入U集、另外一个顶点落入VU集且权值最小的边加入到集合T中，并且将该边的属于VU集的这个顶点加入到U集中，然后继续上述寻找一顶点在U集而另一顶点在VU集且权值最小的边；如此不断重复直到UV时，最小生成树就已经生成，这时集合T中包含了最小生成树中的所有边。PRIM算法能够实现最小生成树构造的理由如下（1）构造过程中对正在生成的最小生成树来说，处于U集中的顶点都是有边相连的顶点，而VU集中的顶点都是没有边相连的顶点，故一个顶点在VU集的边则保证了这个顶点是第一次连接，因此不产生回路；另一个顶点在U集，则保证了生成树构造的连通性，即不会出现不连通的情况。（2）最小生成树的构造过程要进行到U集等于V集为止，即此时U集中的顶点已包含连通网中的全部顶点，由1可知这些顶点都有边相连且又不产生回路，故必为一生成树。（3）在保证（1）的前提下每次都是选取权值最小的边来构造生成树，故最终生成的树为最小生成树。PRIM算法可用下述过程描述WUV表示连接顶点U与顶点V的这条边上的权值（1）UU0，T；（2）WHILEUVU,VMINWUV；UU，VVUTTU,VUUV（3）结束。为实现PRIM算法，需要设置两个一维数组LOWCAST和CLOSEVERTEX；其中，数组LOWCOST用来保存集合VU中各顶点与集合U中各顶点所构成的边中具有最小权值的边的权值，并且一旦将LOWCOSTI置为0，则表示顶点I已加入到集合U中，即该顶点不再作为寻找下一个最小权值边的顶点（只能在VU集中寻找），否则将形成回路；也即，数组LOWCOST有两个功能一个是记录边的权值，一个是标识U集中的顶点。数组CLOSEVERTEX用来保存依附于该边在集合U中的顶点，即若CLOSEVERTEXI的值为J，则表示边I,J中的顶点J在集合U中；数组CLOSEVERTEX同时也保存构造最小生成树过程中产生的每一条边，如CLOSEVERTEXI的值为J，则边I,J即为最小生成树的一条边。我们先设定初始状态UU0（U0为出发的顶点），这时置LOWCOST0为0则表示顶点U0已加入到U集中，数组LOWCOST其它的数组元素值则为顶点U0到其余各顶点边的权值（没有边相连则取一个极大值），同时初始化数组CLOSEVERTEXI所有数组元素值为0（即先假定所有顶点包括U0都与U0有一条边）。然后不断选取权值最小的边UI,UK（UIU，UKVU），每选取一条边就将LOWLOSTK置为0，表示顶点UK已加入到集合U中。由于UK从集合VU进入到集合U，故这两个集合中的顶点发生了变化，所以需要依据这些变化修改数组LOWCOST和数组CLOSEVERTEX中的相关内容。最终数组CLOSEVERTEX中的边即构成一个最小生成树。当连通网采用二维数组存储邻接矩阵时，PRIM算法实现的程序如下INCLUDEDEFINEMAXNODE30DEFINEMAXCOST32767VOIDPRIMINTGM6,INTCLOSEVERTEX,INTN/从存储序号为0的顶点出发建立连通网的最小生成树，GM是邻接矩阵，N为顶点个数（即有0N1个顶点）最终建立的最小生成树存于数组CLOSEVERTEX中/INTLOWCOSTMAXNODEINTI,J,K,MINCOSTFORI1IDEFINEMAXSIZE30DEFINEMAXCOST32767TYPEDEFSTRUCTINTU/边的起始顶点INTV/边的终止顶点INTW/边的权值EDGEVOIDBUBBLESORTEDGER,INTE/冒泡排序/对数组R中的E条边按权值递增排序EDGETEMPINTI,J,SWAPFORI0IRJ1WTEMPRJRJRJ1RJ1TEMP/交换RJ和RJ1SWAP1/置有交换标志IFSWAP0BREAK/本趟比较中未出现交换则结束排序（已排好）VOIDKRUSKALINTGM6,INTN/在顶点为N的连通网中构造最小生成树，GM为连通网的邻接矩阵INTI,J,U1,V1,SN1,SN2,KINTVESTMAXSIZEEDGEEMAXSIZE/MAXSIZE为可存放边数的最大常量值K0FORI0IW1W2（如图728所示）。则将V0VKVU这一路径作为VU新的最短路径。图728顶点V0到顶点VU不同路径长度的比较DIJKSTRA算法的实现是以二维数组GM作为N个顶点带权有向图GV,E的存储结构的，并设置一个一维数组S（下标由0N1）用来标记集合S中已找到最短路径的顶点，而且规定如果SI为0，则表示未找到源点V0到顶点VI的最短路径，也即此时VI在集合T中；如果SI为1，则已找到源点V0到顶点VI的最短路径（此时VI在集合S中）。除了数组S外，还设置了一个数组DIST（下标由0N1），且DISTI用来保存从源点V0到终点VI的当前最短路径长度，它的初值为边上的权值；若V0到VI没有边，则权值为；此后每当有一个新的顶点进入集合S中。则DISTI值可能被修改变小。一维数组PATH（下标由0N1）用于保存最短路径长度中路径上边所经过的顶点序列；其中，PATHI保存从源点V0到终点VI当前最短路径中前一个顶点的编号，它的初值是如果V0到VI有边则置PATHI为V0的编号；如果V0到VI没有边则置PATHI为1。DIJKSTRA算法实现程序如下INCLUDEDEFINEMAXSIZE6/带权有向图中顶点的个数DEFINEINF32767VOIDPPATHINTPATH,INTI,INTV0/先序递归查找最短路径（源点为V0）上的顶点INTKKPATHIIFKV0/顶点VK不是源点V0时PPATHPATH,K,V0/递归查找顶点VK的前一个顶点PRINTF“D,“,K/输出顶点VKVOIDDISPATHINTDIST,INTPATH,INTS,INTV0,INTN/输出最短路径的函数INTIFORI0IDEFINEMAXSIZE6/带权有向图中顶点的个数DEFINEINF32767VOIDPPATHINTPATHMAXSIZE,INTI,INTJ/前向递归查找路径上的顶点，MAXV为常数INTKKPATHIJIFK1/顶点VK不是起点PPATHPATH,I,K/找顶点VI的前一个顶点VKPRINTF“D,“,K/输出顶点VK序号KPPATHPATH,K,J/找顶点VK的前一个顶点VJVOIDDISPATHINTAMAXSIZE,INTPATHMAXSIZE,INTN/输出最短路径的函数INTI,JFORI0IAIKAKJAIJAIKAKJ/从VI到VJ经过VK时路径长度更短PATHIJK/记录中间顶点VK的编号DISPATHGM,PATH,N/输出最短路径VOIDMAININTGMAXSIZEMAXSIZEINF,20,15,INF,INF,INF,2,INF,INF,INF,10,30,INF,4,INF,INF,INF,10,INF,INF,INF,INF,INF,INF,INF,INF,INF,15,INF,INF,INF,INF,INF,4,10,INF/定义邻接矩阵G并给邻接矩阵G赋值FLOYDG,MAXSIZE/求每一对顶点之间的最短路径【说明】主函数MAIN中已存放了图154所示的带权有向图，程序执行如下输出从0到1的路径长度20,路径0,2,1从0到2的路径长度15,路径0,2从0到3没有路径从0到4没有路径从0到5没有路径从1到0的路径长度2,路径1,0从1到2没有路径从1到3没有路径从1到4的路径长度10,路径1,4从1到5的路径长度30,路径1,0,2,5从2到0没有路径从2到1的路径长度4,路径2,1从2到3没有路径从2到4没有路径从2到5的路径长度10,路径2,5从3到0没有路径从3到1没有路径从3到2没有路径从3到4没有路径从3到5没有路径从4到0没有路径从4到1没有路径从4到2没有路径从4到3的路径长度15,路径4,3从4到5没有路径从5到0没有路径从5到1没有路径从5到2没有路径从5到3的路径长度4,路径5,3从5到4的路径长度10,路径5,4PRESSANYKEYTOCONTINUE5拓扑排序和关键路径51AOV网与拓扑排序1AOV网在工程中，一个大的工程通常被划分为许多较小的子工程，这些较小的子工程被称为活动；当这些子工程完成时整个工程也就完成了。我们可以用有向图来描述工程，即在有向图中以顶点来表示活动，用有向边（弧）表示活动之间的优先关系，并称这样的有向图为以顶点表示活动的网（ACTIVITYONVERTEXNETWORK），简称AOV网。在AOV网中，若从顶点VI到顶点VJ之间存在一条有向路径，则称顶点VI是顶点VJ的前驱，顶点VJ是顶点VI的后继。若是网中的一条弧，则称顶点VI是顶点VJ的直接前驱，顶点VJ是顶点VI的直接后继。AOV网中的弧表示了活动之间的优先关系，也即前后制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课学习。学生按怎样的顺序来学习这些课程可以看作是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应的代号如表73所示。表73计算机专业课程设置及其关系表73中，C0、C1是独立于其它课程的基础课，而学习其它课程时必须其先修的课程均已学完，比如在学习过离散数学和程序设计语言课程后才能学习数据结构课程。这些先修条件规定了各课程之间的优先关系；并且，这种优先关系可以用图732的有向图来表示；其中，顶点表示课程，有向边表示前提条件。若课程I为课程J的先修课程则必然存在有向边，在安排学习顺序时，必须保证在学习某门课程之前已经学习了该课程的全部先修课程。课程代号课程名称先修课程代号课程代号课程名称先修课程代号C0C1C2C3C4高等数学程序设计基础离散数学数据结构程序设计语言无无C0,C1C2,C4C1C5C6C7C8编译原理操作系统普通物理计算机原理C3,C4C3,C8C0C7图732课程设置及其关系的AOV网2拓扑排序拓扑排序是将AOV网中所有顶点排成一个线性序列，该线性序列满足下述性质（1）在AOV网中，若顶点VI到顶点VJ有一条路径，则在该线性序列中顶点VI必定在顶点VJ之前。（2）对于网中没有路径的顶点VI与顶点VJ，在线性序列中也建立了一个先后关系；或者顶点VI优先于顶点VJ；或者顶点VJ优先与顶点VI。例如，我们对图732的AOV网进行拓扑排序，至少可得到如下两个（可有多个）拓扑序列（1）C0,C1,C2,C4,C3,C5,C7,C8,C6（2）C0,C7,C8,C1,C4,C2,C3,C6,C5注意，AOV网中不应该出现回路，否则意味着某项活动是以自身的任务完成为先决条件的，这显然是错误的。因此，检测一个工程是否可行必须先检查对应的AOV网是否存在回路；不存在回路的AOV网称为有向无环图或DAG（DIRECTEDACYCLINEGRAPH）图。检测是否存在回路的方法是对有向图构造其顶点的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在回路。图733给出了DAG图与有向图的区别。图733DAG图与有向图的区别构造拓扑序列的过程称为拓扑排序，拓扑排序的序列可能不唯一。若某个AOV网中所有顶点都在它的拓扑序列中，则说明该AOV网不存在回路。显然，对于任何一项工程中各个活动的安排，必须按照拓扑序列中的顺序进行才是可行的。3拓扑排序算法假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是这个工程顺利完成的可行方案。对AOV网进行拓扑排序的算法如下（1）在AOV网中选择一个入度为零（没有前驱）的顶点输出。（2）删除AOV网中该顶点以及与该顶点有关的所有弧。（3）重复（1）、（2）直至网中不存在入度为零的顶点为止。如果算法结束时所有顶点均已输出，则整个拓扑排序完成并说明AOV网中不存在回路；否则表明AOV网中存在回路。图742给出了一个AOV网的拓扑排序过程，所得到的拓扑序列为0,5,3,2,1,4。图734一个AOV网的拓扑排序过程为了实现拓扑排序算法，对AOV网采用邻接表存储结构，但是在邻接表中的顶点结点里增加一个记录顶点入度的数据域，即顶点表结点结构为其中，VERTEX、FIRSTEDGE如722节邻接表所述，而INDEGREE为记录顶点入度的数据域。邻接表结点也同722节所述。顶点表结点结构为TYPEDEFSTRUCTVNODE/顶点表结点/INTINDEGREE/顶点入度/INDEGREEVERTEXFIRSTEDGEINTVERTEX/顶点域/EDGENODEFIRSTEDGE/指向邻接表第一个邻接边结点的指针域/VERTEXNODE/顶点表结点