數(shù)據(jù)結構之圖C源代碼

數(shù)據(jù)結構之圖C源代碼數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第1頁。玩轉算法與數(shù)據(jù)結構之數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第1頁。—HIT2000魯天偉圖在數(shù)據(jù)結構中比前面的鏈表和二叉樹要復雜一些，復雜在無固定的造型。比如讓大家畫一個鏈表，畫一個二叉樹，大家應該畫的差不多一個樣子。但是圖就不行，讓大家畫個圖可能就千差萬別了，我們數(shù)據(jù)結構里面常用的圖是由頂點和邊構成的圖。有長度的邊叫加權邊。由加權邊構成的圖叫帶權圖。研究的無向圖基本上都是連通圖（圖中任意兩個頂點之間都連通，即任兩點間都有一條通路連接）。所研究的有向圖，也是在無向圖的基礎上，在每條邊上加上指示方向的箭頭，并能夠從圖（有向圖按無向圖使用算法）中從任一個頂點開始進行先深搜索（DFS）算法或是先廣搜索（BFS）算法遍歷找到所有頂點。關于圖中度的概念，簡單來說，無向圖頂點的度是指該頂點連接幾條邊，連幾條邊，就是幾度，無向圖中所有頂點的總度數(shù)是邊數(shù)的兩倍。有向圖頂點的度分入度和出度，入度是指向該頂點的邊總和，出度是以該點為起點指向其他頂點的邊總和。無向圖的應用主要是在連通圖中尋找任意頂點到其它頂點間的最短路徑，用最小代價連通各個頂點的最小生成樹。有向圖的應用主要在工程方面，使用AOV（頂點表示活動）網(wǎng)和AOE（邊表示活動）網(wǎng)。AOV網(wǎng)用來表示活動的先后順序，可用拓撲排序來找出活動的先后順序。AOE網(wǎng)用來找出關鍵路徑（從起始點到終止點最長的一條路徑）。AOV和AOE網(wǎng)都是無環(huán)有向圖。圖表SEQ圖表\*ARABIC1無向圖圖表SEQ圖表\*ARABIC2有向圖如上圖1表示無向圖，這個無向圖的邊沒有標明長度，只有鄰接關系?？梢杂绵徑泳仃噥肀硎?，即用一個二維的數(shù)組存放頂點間的關系（表示兩頂點是否有線連接）。鄰接矩陣既可以存無向圖的頂點關系也可以存有向圖的頂點關系。邊沒有長度時，在二維數(shù)組鄰接兩點對應的坐標位置填1表示有鄰接，不鄰接的兩點確定的坐標位置填0表示不鄰接。如果邊有長度設定，可以在坐標位寫入加權邊的長度值。數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第2頁。數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第2頁。圖表SEQ圖表\*ARABIC3鄰接矩陣如上左圖是圖1的鄰接矩陣。右圖是圖2的鄰接矩陣。那么對于有向圖，我們還可以用鄰接表來存儲。即可以用一個一維的地址數(shù)組來存放各頂點指向其它頂點構成的鏈表的頭結點地址。structlist{/*定義鏈表結點結構體*/intdata;/*頂點的序號*/structlist*next;/*指向下一個結點的指針*/};typedefstructlistlistNode;typedeflistNode*link;linkgraph[6];/*有向圖的鄰接表統(tǒng)計頂點出度*/linkreversegraph[6];/*有向圖的逆鄰接表統(tǒng)計頂點入度*/圖表SEQ圖表\*ARABIC4鄰接表如上圖4是鄰接表，比如0指向的頂點是1和4，那么就把1和4形成鏈表，把頭結數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第3頁。點的地址存入指針數(shù)組的0號位置。由此可以方便的找出0指向的頂點，同時也可以統(tǒng)計出0的出度是2。同理，我們可以再作一個逆鄰接表，統(tǒng)計出指向頂點的邊數(shù)，用來統(tǒng)計頂點的入度數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第3頁。圖表SEQ圖表\*ARABIC5逆鄰接表如上圖5就是逆鄰接表，以4為例，有0,1,2,3四個頂點指向4,所以4的出度是4。圖中的8位數(shù)字是結點地址。那么我們嘗試著把鄰接表和逆鄰接表合二為一，于是有了下面的這種十字鏈表。structEdgeList{/*十字鏈表邊結點結構體*/intsource;/*起點值*/intdestination;/*終點值*/structEdgeList*sourcenext;/*起點索引鏈表指針*/structEdgeList*destinationnext;/*終點索引鏈表指針*/};typedefstructEdgeListEdgeListNode;/*結點類型別名*/typedefEdgeListNode*Edgelink;/*結點指針別名*/Edgelinkgraphorth[Max][2];/*4.正交鄰接表二維地址數(shù)組，例：graphorth[i][0]是以i為起點的邊的鏈表首地址，graphorth[i][1]是以i為終點的邊的鏈表首地址*/圖表SEQ圖表\*ARABIC6十字鏈表數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第4頁。如上圖是十字鏈表的黑線連接部分是鄰接表，藍線連接的部分是逆鄰接表。兩個表共用邊結點數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第4頁。那么對于無向圖，也有這樣的應用，可建立鄰接多重表。因為無向圖無關方向，只關注頂點有幾條邊相連接。比如1–2這條邊，既是1相關的邊，也是2相關的邊，2—4這條邊既是2相關的邊，也是4相關的邊。那么1—2和2—4都是2相關的邊，可以建個鏈表，把2相關的邊都連起來，同時1—2也是1相關的邊，所以把這個結點同時加入到1相關的邊鏈表。按此思路，也可以使用十字鏈表的邊結點結構體來完成。圖表SEQ圖表\*ARABIC7鄰接多重表如上圖7鄰接多重表，把一個無向圖的頂點和邊的關系描述的很清楚。如果與頂點相關的邊鏈表的頭結點為空，則把第一條與頂點相關的邊的結點地址寫入到一維地址數(shù)組頂點對應的位置中。后面如果有新增的邊結點，起始點和終止點中包含有頂點。則查看當前與頂點相關的鏈表尾結點中邊的起始點source和終止點destination哪個是頂點。如果source是頂點，則在sourcenext中寫入新增邊結點的地址，如果是destination是頂點，則在destinationnext中寫入新增邊結點的地址。還有一種方法，用一維鄰接數(shù)組，把頂點和邊都加入到一維數(shù)組中。比如數(shù)組位置0代表頂點0,數(shù)組0位置存的6代表，從數(shù)組6位置開始存的是0的鄰接點，位置1存的8代表，從數(shù)組8位置開始存的是1的鄰接點。也就是頂點0的鄰接點是1和2，也就是邊[01]和[02]。頂點1的鄰接點是2和3，也就是邊[12]和[13]以此類推。圖表SEQ圖表\*ARABIC8鄰接數(shù)組。下面來介紹先深搜索遍歷算法（深度優(yōu)先搜索算法）：比如從圖的一個頂點v1開始訪問，v1結點訪問過了，打訪問過的標記（訪問過的結點要打訪問過的標記，最簡單的辦法是用一維數(shù)組）。然后訪問v1的鄰接點，比如是v2，如果沒訪問過則訪問，然后訪問v2的鄰接點。如果v2已經(jīng)訪問過了，則訪問v1的下一個鄰接點。如此使用遞歸方法，可以很好的實現(xiàn)，當然也可以使用棧的方法來實現(xiàn)。如下圖是從頂點1開始的先深搜索頂點訪問順序圖。數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第5頁。數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第5頁。圖表SEQ圖表\*ARABIC9先深搜索頂點訪問順序圖先深搜索算法（遞歸實現(xiàn)，棧實現(xiàn)兩種方法）可執(zhí)行代碼如下：/*====================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){數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第6頁。inti數(shù)據(jù)結構之圖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");}/*===深度優(yōu)先======*/intedgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度優(yōu)先,廣度優(yōu)先算法使用*/linkdeepgraph[9];/*鄰接表*/intvmark[9];/*頂點訪問標記數(shù)組*/intcounter=0;/*訪問頂點計數(shù)*//*===深度優(yōu)先搜索遞歸實現(xiàn)======*/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;}}/*===深度優(yōu)先搜索棧操作=======*//*===入棧======*/數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第7頁。voidpush(int*stack,intdata,int*topaddr數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第7頁。*topaddr=*topaddr+1;stack[*topaddr]=data;}/*===出棧======*/voidpop(int*stack,int*dataaddr,int*topaddr){*dataaddr=stack[*topaddr];*topaddr=*topaddr-1;}/*===深度優(yōu)先搜索棧實現(xiàn)======*/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(){數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第8頁。intsource數(shù)據(jù)結構之圖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============================*/附執(zhí)行結果供參考：數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第9頁。先廣搜索算法（廣度優(yōu)先搜索算法數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第9頁。同先深搜索一樣，比如從圖的一個頂點v1開始訪問，v1結點訪問過了，打訪問過的標記（訪問過的結點要打訪問過的標記，最簡單的辦法是用一維數(shù)組）。以頂點1為起始點為例，訪問過的頂點打訪問過標記。用隊列來實現(xiàn)先廣搜索算法。將1放入到隊列中，查看隊列，如果不空，彈出1個數(shù)據(jù)，彈出數(shù)據(jù)為1，那么訪問1的鄰接表，按順序把未訪問過的頂點加入到隊列中，并標記已訪問。訪問過的頂點略過。查看隊列，如果不空，彈出隊列中第一個數(shù)據(jù)。訪問彈出數(shù)據(jù)的鄰接表，把鄰接表中沒有訪問過的頂點加入隊列，查看隊列，如果不空，再彈出1個數(shù)據(jù)。如此循環(huán)直到隊列為空。下圖是從頂點1開始的先廣搜索頂點訪問順序圖。圖表SEQ圖表\*ARABIC10先廣搜索頂點順序圖先廣搜索算法（隊列實現(xiàn)兩種方法）可執(zhí)行代碼如下：/*====================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;}數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第10頁。else數(shù)據(jù)結構之圖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");}/*===廣度優(yōu)先======*/intedgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度優(yōu)先,廣度優(yōu)先算法使用*/linkdeepgraph[9];/*鄰接表*/intvmark[9];/*頂點訪問標記數(shù)組*/intcounter=0;/*訪問頂點計數(shù)*//*===先廣搜索隊列操作======*//*===入隊======*/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];}/*===廣度優(yōu)先搜索隊列實現(xiàn)======*/intbroadSearch(link*Gr,intindex){linkp=NULL;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第11頁。intqueue[9數(shù)據(jù)結構之圖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);數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第12頁。getch數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第12頁。}/*=====================end============================*/附執(zhí)行結果供參考：最小生成樹：一個有n個結點的連通圖，用最少的邊（n-1條邊）保持圖的連通性，并且所選出的各邊的長度總和最小。最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普里姆）算法求出。Kruskal算法，將所有的加權邊按大小排序，先取長度最小邊，并標記該邊的起始頂點和終止頂點已訪問過。然后從邊鏈表重新選下一條最小的邊，但是這條邊的起始點和終止點不能都是已標記過的，至少有一個頂點沒有標記過。對選出的邊中未標記的頂點進行標記已訪問過。如此反復直至找出n-1條邊。Prim算法，將所有的加權邊按大小排序，先取一個頂點，并標記已訪問過。然后選取包含該頂點的長度最小邊，并標記新選出的邊中未標記的點。然后再選一條最小的邊，但是這條邊的起始點和終止點必須有一個頂點是沒有標記過的，一個頂點是標記過的。對選出的邊中未標記的頂點進行標記已訪問過。如此反復直至找出n-1條邊。圖表SEQ圖表\*ARABIC11最小生成樹數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第13頁。如上圖，選出的邊是圖中紅線。按kruskal算法，選邊的順序是[45]，[34]，[14]，[12]數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第13頁。按prim算法，比如從頂點1開始，選邊的順序是[14]，[4,5]，[3,4]，[1,2]。最小生成樹kruskal和prim算法可執(zhí)行代碼如下：/*====================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;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第14頁。數(shù)據(jù)結構之圖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;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第15頁。}數(shù)據(jù)結構之圖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============================*/執(zhí)行結果如下：數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第16頁。數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第16頁。圖表SEQ圖表\*ARABIC12最短路徑如上圖是起點設定為0，查找0到各頂點的最短路徑，選出的邊是圖中紅線?？梢杂肈ijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法。Dijkstra算法是：采用鄰接矩陣Graph[6][6]，沒有聯(lián)系的兩個頂點形成的邊設為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的前置頂點。循環(huán)執(zhí)行直到所有頂點都被標記過。Floyd算法是：Graph[i][i]=0;(i=0;i<6;i++)，對從頂點i到頂點j的距離，我們?nèi)№旤cu(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）的最短距離，根據(jù)前置頂點數(shù)組的記錄，輸出i到各頂點的前置邊。最短路徑Dijkstra算法和Floyd算法可執(zhí)行代碼如下：/*====================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條邊的圖的初始數(shù)組*/intSmark[6];/*結點標記數(shù)組，1表示已選，0表示未選*/intprenode[Max];/*前置結點數(shù)組*/voidcreateShortpath(int(*Gr)[Max],intsource,intdestination,intweight){/*建無向圖*/Gr[source][destination]=weight;Gr[destination][source]=weight;}voidpush(int*stack,intdata,int*topaddr){*topaddr=*topaddr+1;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第17頁。stack[*topaddr]=data數(shù)據(jù)結構之圖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;/*前置結點數(shù)組初始化為指定的開始結點*/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;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第18頁。for(i=0;i<Max;i++){數(shù)據(jù)結構之圖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;/*前置結點數(shù)組初始化為指定的開始結點*/數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第19頁。數(shù)據(jù)結構之圖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]);}}}數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第20頁。voidmain數(shù)據(jù)結構之圖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++;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第21頁。}while(i<9數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第21頁。index=0;printf("\nFloydShortestPath:\n");shortpathFloyd(graphshortpath,index);getch();}/*=====================end============================*/執(zhí)行結果：關鍵路徑：如下圖是個AOE（ActivityOnEdgeNetwork）網(wǎng)圖即邊表示活動所用時間的無環(huán)有向圖。圖表SEQ圖表\*ARABIC13關鍵路徑AOE網(wǎng)常用于估算工程完成時間，那么在這個圖中找出最長的一條路徑，也叫關鍵路徑，就是決定工程完成時間的路徑，只有縮短這個關鍵路徑上的活動時間，才能縮短整個工程的完成時間。那么如何來找出這條關鍵路徑呢，關鍵路徑的特性是是該路徑最長，且在這個路徑上的頂點的最早開始時間（即從起點開始到各頂點的最長路徑）與最晚開始時間（通過計算各頂點最早開始時間，可以計算出終點的最早開始時間，即關建路徑長度，用這個時間減數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第22頁。去各頂點到終點的最長路徑，即各頂點的最晚開始時間）相等。根據(jù)這些特性能確認出關鏈路徑上的關鍵頂點，從而確定出關鍵路徑，關鍵路徑有時不止一條。在這里面還要說明的是AOE網(wǎng)是無環(huán)有向圖，可以用拓撲排序來判斷一個連通的有向圖是否有環(huán)，如果拓撲排序能輸出所有頂點，則證明無環(huán)，否則有環(huán)。拓撲排序，先找入度為零的頂點，放入數(shù)組中，然后從圖中去除這個點及與其有關的邊。再找入度為零點，放入數(shù)組中，再從圖中去除入度為零的點和相關的邊。以此類推，最后找出所有頂點。上圖中藍色的頂點是關鍵路徑上的頂點，紅色的邊是關鍵路徑的邊。關鍵路徑有兩條：1->3->4->5->7->9和1->3->4->5->8->9數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第22頁。關鍵路徑的可執(zhí)行代碼如下：/*====================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);數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第23頁。p=p->next數(shù)據(jù)結構之圖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條邊的有向圖三維數(shù)組*/linkkeygraphlist[10];/*有向圖的正序鄰接表統(tǒng)計出度*/linkkeyreversegraphlist[10];/*有向圖的反轉鄰接表統(tǒng)計入度*/intKmark[10];/*拓撲結點選中標志*//*===創(chuàng)建有向圖======*/voidcreateKeypath(int(*Gr)[10],intsource,intdestination,intweight){Gr[source][destination]=weight;}/*===入度出度統(tǒng)計======*/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;}}}/*===拓撲排序======*/數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第24頁。inttopo(link*Gr,int*indegree,int*topo){/*topo正序，Gr為鄰接表數(shù)據(jù)結構之圖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;/*即鄰接表中彈出值指向的結點入度統(tǒng)計-1;*/p=p->next;}}elsebreak;}returnj;/*通過這個返回值能判斷圖是否有環(huán)，如果返回值為頂點個數(shù)則無環(huán)，小于頂點個數(shù)則有環(huán)*/}/*===找最長路徑======*/voidlongestpath(link*Gr,int*topo,int*maxdistance,intflag){intindex;intmax;intlength;inti;linkp;maxdistance[topo[1]]=0;數(shù)據(jù)結構之圖C源代碼全文共27頁，當前為第25頁。for(i=2;i<10;i數(shù)據(jù)結構之圖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];/*最早開工時間數(shù)組*/intLatest[10];/*最晚開工時間數(shù)組*/intindegree[10];/*頂點入度統(tǒng)計數(shù)組*/intoutdegree[10];/*頂點出度統(tǒng)計數(shù)組*/inttopoarray[10];in