數(shù)據(jù)結(jié)構(gòu)之圖C源代碼

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