数据结构之图C源代码

数据结构之图C源代码数据结构之图C源代码全文共27页，当前为第1页。玩转算法与数据结构之数据结构之图C源代码全文共27页，当前为第1页。—HIT2000鲁天伟图在数据结构中比前面的链表和二叉树要复杂一些，复杂在无固定的造型。比如让大家画一个链表，画一个二叉树，大家应该画的差不多一个样子。但是图就不行，让大家画个图可能就千差万别了，我们数据结构里面常用的图是由顶点和边构成的图。有长度的边叫加权边。由加权边构成的图叫带权图。研究的无向图基本上都是连通图（图中任意两个顶点之间都连通，即任两点间都有一条通路连接）。所研究的有向图，也是在无向图的基础上，在每条边上加上指示方向的箭头，并能够从图（有向图按无向图使用算法）中从任一个顶点开始进行先深搜索（DFS）算法或是先广搜索（BFS）算法遍历找到所有顶点。关于图中度的概念，简单来说，无向图顶点的度是指该顶点连接几条边，连几条边，就是几度，无向图中所有顶点的总度数是边数的两倍。有向图顶点的度分入度和出度，入度是指向该顶点的边总和，出度是以该点为起点指向其他顶点的边总和。无向图的应用主要是在连通图中寻找任意顶点到其它顶点间的最短路径，用最小代价连通各个顶点的最小生成树。有向图的应用主要在工程方面，使用AOV（顶点表示活动）网和AOE（边表示活动）网。AOV网用来表示活动的先后顺序，可用拓扑排序来找出活动的先后顺序。AOE网用来找出关键路径（从起始点到终止点最长的一条路径）。AOV和AOE网都是无环有向图。图表SEQ图表\*ARABIC1无向图图表SEQ图表\*ARABIC2有向图如上图1表示无向图，这个无向图的边没有标明长度，只有邻接关系。可以用邻接矩阵来表示，即用一个二维的数组存放顶点间的关系（表示两顶点是否有线连接）。邻接矩阵既可以存无向图的顶点关系也可以存有向图的顶点关系。边没有长度时，在二维数组邻接两点对应的坐标位置填1表示有邻接，不邻接的两点确定的坐标位置填0表示不邻接。如果边有长度设定，可以在坐标位写入加权边的长度值。数据结构之图C源代码全文共27页，当前为第2页。数据结构之图C源代码全文共27页，当前为第2页。图表SEQ图表\*ARABIC3邻接矩阵如上左图是图1的邻接矩阵。右图是图2的邻接矩阵。那么对于有向图，我们还可以用邻接表来存储。即可以用一个一维的地址数组来存放各顶点指向其它顶点构成的链表的头结点地址。structlist{/*定义链表结点结构体*/intdata;/*顶点的序号*/structlist*next;/*指向下一个结点的指针*/};typedefstructlistlistNode;typedeflistNode*link;linkgraph[6];/*有向图的邻接表统计顶点出度*/linkreversegraph[6];/*有向图的逆邻接表统计顶点入度*/图表SEQ图表\*ARABIC4邻接表如上图4是邻接表，比如0指向的顶点是1和4，那么就把1和4形成链表，把头结数据结构之图C源代码全文共27页，当前为第3页。点的地址存入指针数组的0号位置。由此可以方便的找出0指向的顶点，同时也可以统计出0的出度是2。同理，我们可以再作一个逆邻接表，统计出指向顶点的边数，用来统计顶点的入度数据结构之图C源代码全文共27页，当前为第3页。图表SEQ图表\*ARABIC5逆邻接表如上图5就是逆邻接表，以4为例，有0,1,2,3四个顶点指向4,所以4的出度是4。图中的8位数字是结点地址。那么我们尝试着把邻接表和逆邻接表合二为一，于是有了下面的这种十字链表。structEdgeList{/*十字链表边结点结构体*/intsource;/*起点值*/intdestination;/*终点值*/structEdgeList*sourcenext;/*起点索引链表指针*/structEdgeList*destinationnext;/*终点索引链表指针*/};typedefstructEdgeListEdgeListNode;/*结点类型别名*/typedefEdgeListNode*Edgelink;/*结点指针别名*/Edgelinkgraphorth[Max][2];/*4.正交邻接表二维地址数组，例：graphorth[i][0]是以i为起点的边的链表首地址，graphorth[i][1]是以i为终点的边的链表首地址*/图表SEQ图表\*ARABIC6十字链表数据结构之图C源代码全文共27页，当前为第4页。如上图是十字链表的黑线连接部分是邻接表，蓝线连接的部分是逆邻接表。两个表共用边结点数据结构之图C源代码全文共27页，当前为第4页。那么对于无向图，也有这样的应用，可建立邻接多重表。因为无向图无关方向，只关注顶点有几条边相连接。比如1–2这条边，既是1相关的边，也是2相关的边，2—4这条边既是2相关的边，也是4相关的边。那么1—2和2—4都是2相关的边，可以建个链表，把2相关的边都连起来，同时1—2也是1相关的边，所以把这个结点同时加入到1相关的边链表。按此思路，也可以使用十字链表的边结点结构体来完成。图表SEQ图表\*ARABIC7邻接多重表如上图7邻接多重表，把一个无向图的顶点和边的关系描述的很清楚。如果与顶点相关的边链表的头结点为空，则把第一条与顶点相关的边的结点地址写入到一维地址数组顶点对应的位置中。后面如果有新增的边结点，起始点和终止点中包含有顶点。则查看当前与顶点相关的链表尾结点中边的起始点source和终止点destination哪个是顶点。如果source是顶点，则在sourcenext中写入新增边结点的地址，如果是destination是顶点，则在destinationnext中写入新增边结点的地址。还有一种方法，用一维邻接数组，把顶点和边都加入到一维数组中。比如数组位置0代表顶点0,数组0位置存的6代表，从数组6位置开始存的是0的邻接点，位置1存的8代表，从数组8位置开始存的是1的邻接点。也就是顶点0的邻接点是1和2，也就是边[01]和[02]。顶点1的邻接点是2和3，也就是边[12]和[13]以此类推。图表SEQ图表\*ARABIC8邻接数组。下面来介绍先深搜索遍历算法（深度优先搜索算法）：比如从图的一个顶点v1开始访问，v1结点访问过了，打访问过的标记（访问过的结点要打访问过的标记，最简单的办法是用一维数组）。然后访问v1的邻接点，比如是v2，如果没访问过则访问，然后访问v2的邻接点。如果v2已经访问过了，则访问v1的下一个邻接点。如此使用递归方法，可以很好的实现，当然也可以使用栈的方法来实现。如下图是从顶点1开始的先深搜索顶点访问顺序图。数据结构之图C源代码全文共27页，当前为第5页。数据结构之图C源代码全文共27页，当前为第5页。图表SEQ图表\*ARABIC9先深搜索顶点访问顺序图先深搜索算法（递归实现，栈实现两种方法）可执行代码如下：/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>structlist{/*定义链表结点结构体*/intdata;/*指向的结点序号*/structlist*next;/*指向下一个结点的指针*/};typedefstructlistlistNode;typedeflistNode*link;/*===建立邻接表===========*/voidcreate_EdgeList(link*Gr,intsource,intdestination){linkp;linknewNode=(link)malloc(sizeof(listNode));newNode->data=destination;newNode->next=NULL;if(Gr[source]==NULL){Gr[source]=newNode;}else{p=Gr[source];while(p->next!=NULL){p=p->next;}p->next=newNode;}}/*===打印邻接表==========*/voidprint_EdgeList(link*Gr,intlen){数据结构之图C源代码全文共27页，当前为第6页。inti数据结构之图C源代码全文共27页，当前为第6页。linkp;for(i=0;i<len;i++){p=Gr[i];printf("%d[%d]:",i,p);while(p!=NULL){printf("%d[%d]",p->data,p->next);p=p->next;}printf("\n");}printf("\n");}/*===深度优先======*/intedgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度优先,广度优先算法使用*/linkdeepgraph[9];/*邻接表*/intvmark[9];/*顶点访问标记数组*/intcounter=0;/*访问顶点计数*//*===深度优先搜索递归实现======*/intdeepSearch(link*Gr,intindex){linkp=NULL;intq;printf("%d",index);vmark[index]=1;counter++;if(counter==8)returncounter;else{p=Gr[index];while(p!=NULL){if(vmark[p->data]==0){q=deepSearch(Gr,p->data);if(q==8)returncounter;}p=p->next;}returncounter;}}/*===深度优先搜索栈操作=======*//*===入栈======*/数据结构之图C源代码全文共27页，当前为第7页。voidpush(int*stack,intdata,int*topaddr数据结构之图C源代码全文共27页，当前为第7页。*topaddr=*topaddr+1;stack[*topaddr]=data;}/*===出栈======*/voidpop(int*stack,int*dataaddr,int*topaddr){*dataaddr=stack[*topaddr];*topaddr=*topaddr-1;}/*===深度优先搜索栈实现======*/intdeepSearchStack(link*Gr,intindex){linkp=NULL;intq=0;intnum;intcounter=0;intstack[9];inttop=-1;printf("%d",index);push(stack,index,&top);vmark[index]=1;counter++;while(top>-1){p=Gr[stack[top]];while(p!=NULL){q=0;if(vmark[p->data]==0){push(stack,p->data,&top);printf("%d",p->data);vmark[p->data]=1;q=1;counter++;break;}elsep=p->next;}if(q==0){pop(stack,&num,&top);}}returncounter;}voidmain(){数据结构之图C源代码全文共27页，当前为第8页。intsource数据结构之图C源代码全文共27页，当前为第8页。intdestination;intresult;inti;do{source=edgesearch[i][0];destination=edgesearch[i][1];create_EdgeList(deepgraph,source,destination);/*把正向的边加入邻接表*/create_EdgeList(deepgraph,destination,source);/*把反向的边也加入邻接表，这是无向图的邻接表建法*/i++;}while(i<10);printf("AdjacencyList:\n");print_EdgeList(deepgraph,9);printf("\nDiGuiDeepSearch:\n");result=deepSearch(deepgraph,1);printf("\nresult=%d\n\n",result);for(i=0;i<9;i++){vmark[i]=0;}printf("\nStackDeepSearch:\n");result=deepSearchStack(deepgraph,1);printf("\nresult=%d\n\n",result);getch();}/*=====================end============================*/附执行结果供参考：数据结构之图C源代码全文共27页，当前为第9页。先广搜索算法（广度优先搜索算法数据结构之图C源代码全文共27页，当前为第9页。同先深搜索一样，比如从图的一个顶点v1开始访问，v1结点访问过了，打访问过的标记（访问过的结点要打访问过的标记，最简单的办法是用一维数组）。以顶点1为起始点为例，访问过的顶点打访问过标记。用队列来实现先广搜索算法。将1放入到队列中，查看队列，如果不空，弹出1个数据，弹出数据为1，那么访问1的邻接表，按顺序把未访问过的顶点加入到队列中，并标记已访问。访问过的顶点略过。查看队列，如果不空，弹出队列中第一个数据。访问弹出数据的邻接表，把邻接表中没有访问过的顶点加入队列，查看队列，如果不空，再弹出1个数据。如此循环直到队列为空。下图是从顶点1开始的先广搜索顶点访问顺序图。图表SEQ图表\*ARABIC10先广搜索顶点顺序图先广搜索算法（队列实现两种方法）可执行代码如下：/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>structlist{/*定义链表结点结构体*/intdata;/*指向的结点序号*/structlist*next;/*指向下一个结点的指针*/};typedefstructlistlistNode;typedeflistNode*link;/*===建立邻接表===========*/voidcreate_EdgeList(link*Gr,intsource,intdestination){linkp;linknewNode=(link)malloc(sizeof(listNode));newNode->data=destination;newNode->next=NULL;if(Gr[source]==NULL){Gr[source]=newNode;}数据结构之图C源代码全文共27页，当前为第10页。else数据结构之图C源代码全文共27页，当前为第10页。p=Gr[source];while(p->next!=NULL){p=p->next;}p->next=newNode;}}/*===打印邻接表==========*/voidprint_EdgeList(link*Gr,intlen){inti;linkp;for(i=0;i<len;i++){p=Gr[i];printf("%d[%d]:",i,p);while(p!=NULL){printf("%d[%d]",p->data,p->next);p=p->next;}printf("\n");}printf("\n");}/*===广度优先======*/intedgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度优先,广度优先算法使用*/linkdeepgraph[9];/*邻接表*/intvmark[9];/*顶点访问标记数组*/intcounter=0;/*访问顶点计数*//*===先广搜索队列操作======*//*===入队======*/voidinqueue(int*queue,int*endaddr,intdata){*endaddr=*endaddr+1;queue[*endaddr]=data;}/*===出队======*/voidoutqueue(int*queue,int*frontaddr,int*temp){*frontaddr=*frontaddr+1;*temp=queue[*frontaddr];}/*===广度优先搜索队列实现======*/intbroadSearch(link*Gr,intindex){linkp=NULL;数据结构之图C源代码全文共27页，当前为第11页。intqueue[9数据结构之图C源代码全文共27页，当前为第11页。intfront=-1;intend=-1;inttemp;intcounter=0;vmark[index]=1;inqueue(queue,&end,index);counter++;while(front!=end){outqueue(queue,&front,&index);printf("%d",index);p=Gr[index];while(p!=NULL){if(vmark[p->data]==0){vmark[p->data]=1;inqueue(queue,&end,p->data);counter++;}p=p->next;}}returncounter;}voidmain(){intsource;intdestination;intresult;inti;do{source=edgesearch[i][0];destination=edgesearch[i][1];create_EdgeList(deepgraph,source,destination);/*把正向的边加入邻接表*/create_EdgeList(deepgraph,destination,source);/*把反向的边也加入邻接表，这是无向图的邻接表建法*/i++;}while(i<10);printf("AdjacencyList:\n");print_EdgeList(deepgraph,9);for(i=0;i<9;i++){vmark[i]=0;}printf("\nQueueBroadSearch:\n");result=broadSearch(deepgraph,1);printf("\nresult=%d\n\n",result);数据结构之图C源代码全文共27页，当前为第12页。getch数据结构之图C源代码全文共27页，当前为第12页。}/*=====================end============================*/附执行结果供参考：最小生成树：一个有n个结点的连通图，用最少的边（n-1条边）保持图的连通性，并且所选出的各边的长度总和最小。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。Kruskal算法，将所有的加权边按大小排序，先取长度最小边，并标记该边的起始顶点和终止顶点已访问过。然后从边链表重新选下一条最小的边，但是这条边的起始点和终止点不能都是已标记过的，至少有一个顶点没有标记过。对选出的边中未标记的顶点进行标记已访问过。如此反复直至找出n-1条边。Prim算法，将所有的加权边按大小排序，先取一个顶点，并标记已访问过。然后选取包含该顶点的长度最小边，并标记新选出的边中未标记的点。然后再选一条最小的边，但是这条边的起始点和终止点必须有一个顶点是没有标记过的，一个顶点是标记过的。对选出的边中未标记的顶点进行标记已访问过。如此反复直至找出n-1条边。图表SEQ图表\*ARABIC11最小生成树数据结构之图C源代码全文共27页，当前为第13页。如上图，选出的边是图中红线。按kruskal算法，选边的顺序是[45]，[34]，[14]，[12]数据结构之图C源代码全文共27页，当前为第13页。按prim算法，比如从顶点1开始，选边的顺序是[14]，[4,5]，[3,4]，[1,2]。最小生成树kruskal和prim算法可执行代码如下：/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>intmingraph[10][3]={1,2,7,1,3,6,1,4,5,1,5,12,2,3,14,2,4,8,2,5,8,3,4,3,3,5,9,4,5,2};intMmark[9];structmintree{intmarked;intsource;intdestination;intweight;structmintree*next;};typedefstructmintreemtree;typedefmtree*mlink;mlinkcreateMtree(mlinkhead,intsource,intdestination,intweight){/*边排序*/mlinkp;mlinkq;mlinknewNode=(mlink)malloc(sizeof(mtree));newNode->marked=0;newNode->source=source;newNode->destination=destination;newNode->weight=weight;newNode->next=NULL;if(head==NULL)head=newNode;else{if(weight<head->weight){newNode->next=head;head=newNode;}else{p=head;q=head->next;while(q!=NULL){if(weight<q->weight){newNode->next=q;p->next=newNode;break;数据结构之图C源代码全文共27页，当前为第14页。数据结构之图C源代码全文共27页，当前为第14页。else{p=q;q=q->next;}}if(q==NULL)p->next=newNode;}}returnhead;}/*kruskal算法*/voidkruskal(mlinkhead,intEdge){intedge=0;mlinkp=NULL;p=head;while(p!=NULL&edge<Edge){if(Mmark[p->source]==0||Mmark[p->destination]==0){Mmark[p->source]=1;Mmark[p->destination]=1;printf("[%d%d]",p->source,p->destination);edge++;}p=p->next;}}/*prim算法*/voidprim(mlinkhead,intEdge,intindex){intedge=0;mlinkp=NULL;intmin;mlinkq;Mmark[index]=1;while(edge<Edge){p=head;min=999;while(p!=NULL){if((Mmark[p->source]^Mmark[p->destination])==1)if(p->weight<min){min=p->weight;q=p;}p=p->next;数据结构之图C源代码全文共27页，当前为第15页。}数据结构之图C源代码全文共27页，当前为第15页。Mmark[q->source]=1;Mmark[q->destination]=1;printf("[%d%d]",q->source,q->destination);edge++;}}voidmain(){inti=0;intsource;intdestination;intweight;mlinkhead=NULL;do{source=mingraph[i][0];destination=mingraph[i][1];weight=mingraph[i][2];head=createMtree(head,source,destination,weight);i++;}while(i<10);printf("\nKruskalMinimumSpanningTree:\n");kruskal(head,4);printf("\n");for(i=0;i<9;i++){Mmark[i]=0;}printf("\nPrimMinimumSpanningTree:\n");prim(head,4,1);printf("\n");getch();}/*=====================end============================*/执行结果如下：数据结构之图C源代码全文共27页，当前为第16页。数据结构之图C源代码全文共27页，当前为第16页。图表SEQ图表\*ARABIC12最短路径如上图是起点设定为0，查找0到各顶点的最短路径，选出的边是图中红线。可以用Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法。Dijkstra算法是：采用邻接矩阵Graph[6][6]，没有联系的两个顶点形成的边设为999这个值。先对开始的顶点v1标记已访问，然后再选一个点v2，[v1v2]是v1到其它所有顶点中最短的这条边。标记v2已访问过，计算v1通过v2到其它顶点v3（指v2到v3有边且边长不等于999且v3没有标记过的情况）的距离，如果比直接从v1到v3的距离短，则用v1到v2的距离与v2到v3的距离之和来替代v1到v3的距离，写入到邻接矩阵，标记v3为v2的前置顶点。计算替换完所有可以计算的v3类顶点。同上面对v2的操作，再选一个新的顶点v4（未标记过的），在未标记过的顶点中，[v1v4]是边长最短的。标记v4然后计算v1通过v4到其它未标记顶点v5的新距离。如果新距离比从v1直接到达更短，则替换v1到对应顶点v5的距离，标记v4为v5的前置顶点。循环执行直到所有顶点都被标记过。Floyd算法是：Graph[i][i]=0;(i=0;i<6;i++)，对从顶点i到顶点j的距离，我们取顶点u(0=<u<max);如Graph[i][u]+Graph[u][j]<Graph[i][j]则用Graph[i][j]=Graph[i][u]+Graph[u][j]。标记u为j的前置顶点。全部计算完后，输出i到j（0<=j<max）的最短距离，根据前置顶点数组的记录，输出i到各顶点的前置边。最短路径Dijkstra算法和Floyd算法可执行代码如下：/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>#defineMax6intgraphshortpath[Max][Max];/*图的邻接距阵，用来存放边长*/intedgeshortpath[9][3]={0,1,6,0,2,3,2,1,2,1,3,5,2,3,3,2,4,4,3,4,2,3,5,3,4,5,5};/*6个顶点9条边的图的初始数组*/intSmark[6];/*结点标记数组，1表示已选，0表示未选*/intprenode[Max];/*前置结点数组*/voidcreateShortpath(int(*Gr)[Max],intsource,intdestination,intweight){/*建无向图*/Gr[source][destination]=weight;Gr[destination][source]=weight;}voidpush(int*stack,intdata,int*topaddr){*topaddr=*topaddr+1;数据结构之图C源代码全文共27页，当前为第17页。stack[*topaddr]=data数据结构之图C源代码全文共27页，当前为第17页。}voidpop(int*stack,int*dataaddr,int*topaddr){*dataaddr=stack[*topaddr];*topaddr=*topaddr-1;}voidshortpathDijkstra(int(*Gr)[Max],intindex){intp,q;intcounter=0;intmin;inti;intstack[6];/*用来输出连串的前置结点*/inttop=-1;inttemp;Smark[index]=1;min=999;for(i=0;i<Max;i++){prenode[i]=index;/*前置结点数组初始化为指定的开始结点*/if(Gr[index][i]!=999&&Gr[index][i]<min){/*在紧邻index的顶点中找最小值*/min=Gr[index][i];p=i;}}printf("%d->%d",index,p);Smark[p]=1;counter++;while(counter<5){for(i=0;i<Max;i++){if(Gr[p][i]!=999&&Smark[i]==0){temp=Gr[index][p]+Gr[p][i];/*计算index结点通过新增前置结点能到达的未标记结点的距离*/if(temp<Gr[index][i]){/*如果计算的距离比当前的距离小*/Gr[index][i]=temp;/*距离替换*/prenode[i]=p;/*前置结点替换*/printf("%d->%d",p,i);}}}min=999;数据结构之图C源代码全文共27页，当前为第18页。for(i=0;i<Max;i++){数据结构之图C源代码全文共27页，当前为第18页。if(Smark[i]==0){if(Gr[index][i]<min){min=Gr[index][i];q=i;/*找出index结点到达所有未标记结点距离最短的点*/}}}Smark[q]=1;counter++;p=q;}printf("\n");for(i=0;i<Max;i++){if(i!=index){printf("[%d->%d%d]",index,i,Gr[index][i]);}}printf("\n");for(i=0;i<Max;i++){if(i!=index){push(stack,i,&top);p=prenode[i];while(p!=index){push(stack,p,&top);p=prenode[p];}printf("%d->",index);while(top!=-1){pop(stack,&p,&top);printf("%d->",p);}printf("[%d->%dlength=%d]\n",index,i,Gr[index][i]);}}}voidshortpathFloyd(int(*Gr)[Max],intindex){inti,j,u;intstack[6];/*栈用来输出连串的前置结点*/inttop=-1;intp;for(i=0;i<Max;i++){prenode[i]=index;/*前置结点数组初始化为指定的开始结点*/数据结构之图C源代码全文共27页，当前为第19页。数据结构之图C源代码全文共27页，当前为第19页。for(i=0;i<Max;i++){Gr[i][i]=0;}for(u=0;u<Max;u++){for(i=0;i<Max;i++){for(j=0;j<Max;j++){if(Gr[i][u]+Gr[u][j]<Gr[i][j]){Gr[i][j]=Gr[i][u]+Gr[u][j];if(i==index){prenode[j]=u;printf("%d->%d",u,j);}}}}}printf("\n");for(i=0;i<Max;i++){if(i!=index){printf("[%d->%d%d]",index,i,Gr[index][i]);}}printf("\n");for(i=0;i<Max;i++){if(i!=index){push(stack,i,&top);p=prenode[i];while(p!=index){push(stack,p,&top);p=prenode[p];}printf("%d->",index);while(top!=-1){pop(stack,&p,&top);printf("%d->",p);}printf("[%d->%dlength=%d]\n",index,i,Gr[index][i]);}}}数据结构之图C源代码全文共27页，当前为第20页。voidmain数据结构之图C源代码全文共27页，当前为第20页。inti;intj;intsource;intdestination;intweight;intindex;for(i=0;i<Max;i++){for(j=0;j<Max;j++){graphshortpath[i][j]=999;}}i=0;do{source=edgeshortpath[i][0];destination=edgeshortpath[i][1];weight=edgeshortpath[i][2];createShortpath(graphshortpath,source,destination,weight);i++;}while(i<9);for(i=0;i<Max;i++){for(j=0;j<Max;j++){printf("%3d",graphshortpath[i][j]);}printf("\n");}index=0;printf("\nDijkstraShortestPath:\n");shortpathDijkstra(graphshortpath,index);for(i=0;i<Max;i++){for(j=0;j<Max;j++){graphshortpath[i][j]=999;}}i=0;do{source=edgeshortpath[i][0];destination=edgeshortpath[i][1];weight=edgeshortpath[i][2];createShortpath(graphshortpath,source,destination,weight);i++;数据结构之图C源代码全文共27页，当前为第21页。}while(i<9数据结构之图C源代码全文共27页，当前为第21页。index=0;printf("\nFloydShortestPath:\n");shortpathFloyd(graphshortpath,index);getch();}/*=====================end============================*/执行结果：关键路径：如下图是个AOE（ActivityOnEdgeNetwork）网图即边表示活动所用时间的无环有向图。图表SEQ图表\*ARABIC13关键路径AOE网常用于估算工程完成时间，那么在这个图中找出最长的一条路径，也叫关键路径，就是决定工程完成时间的路径，只有缩短这个关键路径上的活动时间，才能缩短整个工程的完成时间。那么如何来找出这条关键路径呢，关键路径的特性是是该路径最长，且在这个路径上的顶点的最早开始时间（即从起点开始到各顶点的最长路径）与最晚开始时间（通过计算各顶点最早开始时间，可以计算出终点的最早开始时间，即关建路径长度，用这个时间减数据结构之图C源代码全文共27页，当前为第22页。去各顶点到终点的最长路径，即各顶点的最晚开始时间）相等。根据这些特性能确认出关链路径上的关键顶点，从而确定出关键路径，关键路径有时不止一条。在这里面还要说明的是AOE网是无环有向图，可以用拓扑排序来判断一个连通的有向图是否有环，如果拓扑排序能输出所有顶点，则证明无环，否则有环。拓扑排序，先找入度为零的顶点，放入数组中，然后从图中去除这个点及与其有关的边。再找入度为零点，放入数组中，再从图中去除入度为零的点和相关的边。以此类推，最后找出所有顶点。上图中蓝色的顶点是关键路径上的顶点，红色的边是关键路径的边。关键路径有两条：1->3->4->5->7->9和1->3->4->5->8->9数据结构之图C源代码全文共27页，当前为第22页。关键路径的可执行代码如下：/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>structlist{/*定义链表结点结构体*/intdata;/*指向的结点序号*/structlist*next;/*指向下一个结点的指针*/};typedefstructlistlistNode;typedeflistNode*link;/*===建立邻接表===========*/voidcreate_EdgeList(link*Gr,intsource,intdestination){linkp;linknewNode=(link)malloc(sizeof(listNode));newNode->data=destination;newNode->next=NULL;if(Gr[source]==NULL){Gr[source]=newNode;}else{p=Gr[source];while(p->next!=NULL){p=p->next;}p->next=newNode;}}/*===打印邻接表==========*/voidprint_EdgeList(link*Gr,intlen){inti;linkp;for(i=0;i<len;i++){p=Gr[i];printf("%d[%d]:",i,p);while(p!=NULL){printf("%d[%d]",p->data,p->next);数据结构之图C源代码全文共27页，当前为第23页。p=p->next数据结构之图C源代码全文共27页，当前为第23页。}printf("\n");}printf("\n");}/*===入队======*/voidinqueue(int*queue,int*endaddr,intdata){*endaddr=*endaddr+1;queue[*endaddr]=data;}/*===出队======*/voidoutqueue(int*queue,int*frontaddr,int*temp){*frontaddr=*frontaddr+1;*temp=queue[*frontaddr];}/*关键路径*/intgraphkeypath[10][10];intedgekeypath[13][3]={1,2,5,1,3,7,2,4,3,3,4,6,3,5,3,4,5,4,4,6,4,4,7,4,5,7,2,5,8,5,7,9,5,6,9,4,8,9,2};/*9个顶点13条边的有向图三维数组*/linkkeygraphlist[10];/*有向图的正序邻接表统计出度*/linkkeyreversegraphlist[10];/*有向图的反转邻接表统计入度*/intKmark[10];/*拓扑结点选中标志*//*===创建有向图======*/voidcreateKeypath(int(*Gr)[10],intsource,intdestination,intweight){Gr[source][destination]=weight;}/*===入度出度统计======*/voiddegreestatic(link*Gr,int*degree){inti;for(i=1;i<10;i++){linkp;p=Gr[i];while(p!=NULL){degree[i]=degree[i]+1;p=p->next;}}}/*===拓扑排序======*/数据结构之图C源代码全文共27页，当前为第24页。inttopo(link*Gr,int*indegree,int*topo){/*topo正序，Gr为邻接表数据结构之图C源代码全文共27页，当前为第24页。inti;intj=0;intindex=1;intqueue[10];intfront=-1;intend=-1;linkp=NULL;inttemp;while(1){for(i=1;i<10;i++){if(indegree[i]==0&&Kmark[i]==0){/*在indegree中找出入度为零的点入队列*/inqueue(queue,&end,i);Kmark[i]=1;}}if(front!=end){outqueue(queue,&front,&temp);/*队列不空出队操作*/topo[index++]=temp;j++;p=Gr[temp];while(p!=NULL){indegree[p->data]=indegree[p->data]-1;/*即邻接表中弹出值指向的结点入度统计-1;*/p=p->next;}}elsebreak;}returnj;/*通过这个返回值能判断图是否有环，如果返回值为顶点个数则无环，小于顶点个数则有环*/}/*===找最长路径======*/voidlongestpath(link*Gr,int*topo,int*maxdistance,intflag){intindex;intmax;intlength;inti;linkp;maxdistance[topo[1]]=0;数据结构之图C源代码全文共27页，当前为第25页。for(i=2;i<10;i数据结构之图C源代码全文共27页，当前为第25页。index=topo[i];p=Gr[index];max=-1;while(p!=NULL){if(flag==0)/*使用拓朴正序，反向邻接表*/length=maxdistance[p->data]+graphkeypath[p->data][index];/*计算前置结点到index距离*/else/*使用拓扑逆序，正向邻接表*/length=maxdistance[p->data]+graphkeypath[index][p->data];/*计算index到后置结点的距离*/if(length>max)max=length;p=p->next;}maxdistance[index]=max;/*保存最大距离*/}}/*===关键路径输出======*/voidkeypath(link*keygraphlist,link*keyreversegraphlist){inti;intEarlist[10];/*最早开工时间数组*/intLatest[10];/*最晚开工时间数组*/intindegree[10];/*顶点入度统计数组*/intoutdegree[10];/*顶点出度统计数组*/inttopoarray[10];in