圖的基本操作及應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc

算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告系 （院）： 計(jì)算機(jī)科學(xué)學(xué)院 專業(yè)班級： 教育技術(shù)學(xué)1001班 姓 名： 宋佳 學(xué) 號： 201003901 指導(dǎo)教師： 詹澤梅 設(shè)計(jì)時(shí)間： 2012.6.16 - 2012.6.24 設(shè)計(jì)地點(diǎn)： 4號樓2號機(jī)房 算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書班級：教育技術(shù)11001課程設(shè)計(jì)題目：圖的基本操作及應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。本實(shí)踐教學(xué)是培養(yǎng)學(xué)生數(shù)據(jù)抽象能力，進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程。要求學(xué)生能對所涉及問題選擇合適的數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)及算法，并編寫出結(jié)構(gòu)清楚且正確易讀的程序，提高程序設(shè)計(jì)基本技能和技巧。一設(shè)計(jì)目的1提高數(shù)據(jù)抽象能力。根據(jù)實(shí)際問題，能利用數(shù)據(jù)結(jié)構(gòu)理論課中所學(xué)到的知識選擇合適的邏輯結(jié)構(gòu)以及存儲結(jié)構(gòu)，并設(shè)計(jì)出有效解決問題的算法。2提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。3初步了解開發(fā)過程中問題分析、整體設(shè)計(jì)、程序編碼、測試等基本方法和技能。二設(shè)計(jì)任務(wù)設(shè)計(jì)一個(gè)基于DOS菜單的應(yīng)用程序。要利用多級菜單實(shí)現(xiàn)各種功能。內(nèi)容如下：1 無向圖的基本操作及應(yīng)用 創(chuàng)建無向圖的鄰接矩陣 創(chuàng)建無向圖的鄰接表 無向圖的深度優(yōu)先遍歷 無向圖的廣度優(yōu)先遍歷2 有向圖的基本操作及應(yīng)用 創(chuàng)建有向圖的鄰接矩陣 創(chuàng)建有向圖的鄰接表 拓?fù)渑判? 無向網(wǎng)的基本操作及應(yīng)用 創(chuàng)建無向網(wǎng)的鄰接矩陣 創(chuàng)建無向網(wǎng)的鄰接表 求最小生成樹 4 有向網(wǎng)的基本操作及應(yīng)用 創(chuàng)建有向網(wǎng)的鄰接矩陣 創(chuàng)建有向網(wǎng)的鄰接表 關(guān)鍵路徑 單源最短路徑 三設(shè)計(jì)指導(dǎo)第一步：根據(jù)設(shè)計(jì)任務(wù)，設(shè)計(jì)DOS菜單。第二步：設(shè)計(jì)菜單（c語言）#includevoid ShowMainMenu()printf(n);printf(*圖的基本操作及應(yīng)用*n);printf(* 1 無向圖的基本操作及應(yīng)用 *n);printf(* 2 有向圖的基本操作及應(yīng)用 *n);printf(* 3 無向網(wǎng)的基本操作及應(yīng)用 *n);printf(* 4 有向網(wǎng)的基本操作及應(yīng)用 *n);printf(* 5 退出n);printf(*n);void UDG()int n;doprintf(n);printf(*無向圖的基本操作及應(yīng)用*n);printf(* 1 創(chuàng)建無向圖的鄰接矩陣 *n);printf(* 2 創(chuàng)建無向圖的鄰接表 *n);printf(* 3 無向圖的深度優(yōu)先遍歷 *n);printf(* 4 無向圖的廣度優(yōu)先遍歷 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DG() int n;doprintf(n);printf(*有向圖的基本操作及應(yīng)用*n);printf(* 1 創(chuàng)建有向圖的鄰接矩陣 *n);printf(* 2 創(chuàng)建有向圖的鄰接表 *n);printf(* 3 拓?fù)渑判?*n);printf(* 4 退出 *n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:break;default:printf(ERROR!);while(n!=4);void UDN() int n;doprintf(n);printf(*無向網(wǎng)的基本操作及 *n);printf(* 1 創(chuàng)建無向網(wǎng)的鄰接矩陣 *n);printf(* 2 創(chuàng)建無向網(wǎng)的鄰接表 *n);printf(* 3 Prim算法求最小生成樹 *n);printf(* 4 kraskal算法求最小生成樹 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(- -wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DN() int n;doprintf(n);printf(*有向網(wǎng)的基本操作*n);printf(* 1 創(chuàng)建有向網(wǎng)的鄰接矩陣 *n);printf(* 2 創(chuàng)建有向網(wǎng)的鄰接表 *n);printf(* 3 關(guān)鍵路徑 *n);printf(* 4 單源頂點(diǎn)最短路徑問題 *n);printf(* 5 退出n);printf(*n);printf(請選擇：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void main()int n;doShowMainMenu();printf(請選擇：);scanf(%d,&n);switch(n)case 1:UDG();break;case 2:DG();break;case 3:UDN();break;case 4:DN();break;case 5:break;default:printf(ERROR!);break;while(n!=5);第三步：添加功能函數(shù)。在主程序的合適位置添加相應(yīng)的函數(shù)實(shí)現(xiàn)各功能（提示：語句printf(“-wait-”)所在位置）。四成績評定l 實(shí)習(xí)報(bào)告（文字不得少于4000字）一、 設(shè)計(jì)方案；二、 實(shí)現(xiàn)過程；三、 實(shí)現(xiàn)代碼；四、 測試；五、 結(jié)論；六、 難點(diǎn)與收獲。l 程序?qū)崿F(xiàn)1. 程序運(yùn)行正確，無編譯錯(cuò)誤，無邏輯錯(cuò)誤；2. 在第一條的基礎(chǔ)上，任務(wù)完成的越多，成績等級越高。l 成績由三部分組成：平時(shí)考核(20%)、程序?qū)崿F(xiàn)(50%)、實(shí)習(xí)報(bào)告(30%)一、 設(shè)計(jì)方案由課程設(shè)計(jì)任務(wù)書，按照要求，需要設(shè)計(jì)有向圖3、有向網(wǎng)、無向圖 、無向網(wǎng)四種圖，鄰接矩陣、鄰接表兩種數(shù)據(jù)存儲結(jié)構(gòu)，共十六種基本操作及應(yīng)用，三層以上的顯示菜單。圖的操作中又包含有有關(guān)線性表、棧和隊(duì)列的基本操作。由于顯示菜單已給出，剩下的只是把函數(shù)寫入其中，而線性表、棧和隊(duì)列的基本操作并不復(fù)雜，很容易實(shí)現(xiàn)，我們只有完成圖的相關(guān)操作即可。圖的操作都是以兩種存儲結(jié)構(gòu)為基礎(chǔ)的，鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)，如四種圖（有向圖，有向網(wǎng)，無向圖，無向網(wǎng)）的創(chuàng)建，其他的操作都是在四種圖創(chuàng)建后才開始進(jìn)行的。所以，首先必須理解兩種存儲結(jié)構(gòu)的定義。圖的鄰接矩陣存儲結(jié)構(gòu)即圖的數(shù)組表示法。用兩個(gè)數(shù)組分別存儲數(shù)據(jù)元素（頂點(diǎn)）的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔?。用鄰接矩陣存儲結(jié)構(gòu)的圖具有以下幾點(diǎn)特征：（一）：頂點(diǎn)數(shù)：vexnum，邊（?。?shù)：arcnum，圖的種類：kind；（二）：鄰接矩陣：arcs(1頂點(diǎn)關(guān)系類型:adj 2相關(guān)信息:*info)；（三）：頂點(diǎn)向量（頂點(diǎn)名）：vexs；其優(yōu)點(diǎn)是以二維數(shù)組表示有n個(gè)頂點(diǎn)的圖時(shí)，需存放n頂點(diǎn)的信息和n*n個(gè)弧的信息存儲量。借助于鄰接矩陣容易判定任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，并容易求各個(gè)頂點(diǎn)的度。缺點(diǎn)其時(shí)間復(fù)雜度是O（n*n）,例如，構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向網(wǎng)的時(shí)間復(fù)雜度為O（n*n+e*n）。圖的鄰接表存儲結(jié)構(gòu)是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，每個(gè)結(jié)點(diǎn)有三個(gè)域組成，鄰接點(diǎn)域adjvex（弧尾在鄰接表鏈表中的位序），鏈域nextarc（下一條?。?，數(shù)據(jù)域info(權(quán)值)。還要建立一個(gè)鄰接表鏈表，用以存放頂點(diǎn)名data和后繼指針firstarc,表頭結(jié)點(diǎn)以順序結(jié)構(gòu)的形式存儲，便于隨機(jī)訪問任一頂點(diǎn)的單鏈表。鄰接表存儲結(jié)構(gòu)的優(yōu)點(diǎn)在于其時(shí)間復(fù)雜度小。除此之外，還有十字鏈表存儲結(jié)構(gòu)和多重鏈表存儲結(jié)構(gòu)。由于，沒有用到他們，故不再詳細(xì)描述。樹的深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。從圖中的某個(gè)頂點(diǎn)出發(fā)，訪問此頂點(diǎn)，然后依次從該頂點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有與該頂點(diǎn)有關(guān)的路徑都被訪問到；此時(shí)圖中若還有頂點(diǎn)未被訪問到，則另選圖中的一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重述上述過程，直至所有頂點(diǎn)都被訪問到。廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。以某個(gè)頂點(diǎn)為起始頂點(diǎn)，由近至遠(yuǎn)，依次訪問和該頂點(diǎn)有路徑相通的且路徑長度為1， 2， 3，的頂點(diǎn)。當(dāng)圖中所有頂點(diǎn)都被訪問到后，就完成了圖的廣度優(yōu)先搜索遍歷。求無向網(wǎng)的最小生成樹問題有兩種算法：Prima算法和Kruskal算法。Prima算法是從網(wǎng)中的某個(gè)頂點(diǎn)出發(fā)，選擇與該頂點(diǎn)有路徑的所有頂點(diǎn)中路徑最小的一條路徑，從該最小路徑的另一頂點(diǎn)出發(fā)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問完成。Kruskal算法是從網(wǎng)中找出所有路徑最小的一條路徑，記下已訪問該路徑的兩個(gè)頂點(diǎn)，再次從圖中找出剩下路徑中的最小路徑，重復(fù)上述過程，直至所有頂點(diǎn)都被訪問完成，按訪問的順序依次輸出各頂點(diǎn)，即構(gòu)造了一棵最小生成樹。由某個(gè)集合上的一個(gè)偏序得到該集合的一個(gè)全序的操作就叫做拓?fù)渑判颉Ｍ負(fù)渑判蛑饕袃蓚€(gè)方面的操作：（1）在有向圖中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并輸出；（2）在圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，就得到了一個(gè)拓?fù)溆行蛐蛄?。求關(guān)鍵路徑的算法如下：輸入e條弧，建立AOE網(wǎng)的存儲結(jié)構(gòu)；從源點(diǎn)v0出發(fā),令ve0=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間。如果得到的拓?fù)溆行蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)中的頂點(diǎn)數(shù)，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行第三步。從匯點(diǎn)vn出發(fā)，令vln-1=ven-1，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vli；根據(jù)各頂點(diǎn)的和值，求每條弧的最早開始時(shí)間e(s)和最遲開始時(shí)間e(s)，若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)。從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問題：若從v到vi有弧，則Di為弧上的權(quán)值，否則Di為無窮大。顯然，長度為Dj=MinDi|vi屬于V的路徑就是從v出發(fā)的長度最短的一條路徑。二、 實(shí)現(xiàn)及測試過程按照設(shè)計(jì)任務(wù)的要求，我先完成了存儲結(jié)點(diǎn)、邊、鄰接矩陣、鄰接表、隊(duì)列、棧等儲存結(jié)構(gòu)體的設(shè)計(jì)。其次是棧和隊(duì)列的基本操作和實(shí)現(xiàn)，四種圖的創(chuàng)建和顯示，然后是基于兩種存儲結(jié)構(gòu)的各種算法的現(xiàn)，最后是三層顯示輸出菜單。測試樣圖：三、實(shí)現(xiàn)代碼#include #include#include #define ERROR 0#define OK 1#define INFINITY INT_MAX#define MAX_VERTEX_NUM 21#define STACK_INIT_SIZE 100#define STACKINCREAMENT 10typedef enumDG,DN,UDG,UDNGraphKind;typedef struct ArcCell int adj; /infotype *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind;MGraph; /鄰接矩陣typedef struct ArcNode int adjvex; int quan; struct ArcNode *nextarc; ArcNode,*AList;typedef struct VNode char data; AList firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; GraphKind kind;ALGraph; /鄰接表typedef struct QNodechar data;struct QNode *next;QNode,*QueuePre;typedef structQueuePre front;QueuePre rear;LinkQueue; /隊(duì)列typedef struct int *base;int *top;int stacksize;SqStack; /棧typedef struct char adjvex;int lowcost;closedgesMAX_VERTEX_NUM; /求最小生成樹中的輔助數(shù)組int option; int visitedMAX_VERTEX_NUM; /頂點(diǎn)訪問標(biāo)記數(shù)組int indegreeMAX_VERTEX_NUM; /頂點(diǎn)入度記錄數(shù)組int veMAX_VERTEX_NUM; /頂點(diǎn)權(quán)值記錄數(shù)組int SetGraphKind(MGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /鄰接矩陣類型設(shè)置int SetGraphKind(ALGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /鄰接表類型設(shè)置int LocateVex(MGraph G,char v) int m; for(m=1;m=G.vexnum;m+) if(G.vexsm=v) return m; return ERROR; /鄰接矩陣頂點(diǎn)定位int LocateVex(ALGraph G,char v) int m; for(m=1;mnext=NULL;return OK; /隊(duì)列創(chuàng)建int EnQueue(LinkQueue &Q,int e)QueuePre p;p=(QueuePre)malloc(sizeof(QNode);if(!p) return OK;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; /元素入隊(duì)列int DeQueue(LinkQueue &Q,int &e)QueuePre p;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK; /元素出隊(duì)列int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return OK;return ERROR; /判斷隊(duì)列是否為空int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /棧創(chuàng)建int Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;*S.top+=e;return OK; /元素入棧int Pop(SqStack &S,int &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK; /元素出棧int StackEmpty(SqStack S)if(S.top=S.base) return OK;return ERROR; /判斷棧是否為空int CreatGraph(MGraph &G) int i,j,k,w;char x,y; if(!SetGraphKind(G,option) printf(對圖類型的設(shè)置失敗);return ERROR; printf(鄰接矩陣：請輸入定點(diǎn)的個(gè)數(shù)、弧的個(gè)數(shù)：); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum20) printf(您輸入的頂點(diǎn)個(gè)數(shù)超過最大值); return ERROR; printf(請輸入%d個(gè)頂點(diǎn)n,G.vexnum); for(i=1;i=G.vexnum;+i) fflush(stdin); scanf(%c,&G.vexsi); if(G.kind=DG|G.kind=UDG) for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=0; if(G.kind=DG) printf(請輸入有向圖的兩個(gè)相鄰的頂點(diǎn)（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x);j=LocateVex(G,y); G.arcsij.adj=1; else printf(請輸入無向圖的兩個(gè)相鄰的頂點(diǎn)（x,y）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=1; G.arcsji.adj=G.arcsij.adj; else for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=INT_MAX; if(G.kind=DN) printf(請輸入有向網(wǎng)的兩個(gè)相鄰的頂點(diǎn)以及相應(yīng)的權(quán)值w（如果互相鄰接則也要輸入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c %d,&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=w; else printf(請輸入無向網(wǎng)的兩個(gè)相鄰的頂點(diǎn)（x,y）以及相應(yīng)的權(quán)值w：n); for(k=1;k20) printf(您輸入的頂點(diǎn)個(gè)數(shù)超過最大值); return ERROR; printf(請輸入個(gè)頂點(diǎn)：n);for(i=1;i=G.vexnum;i+)fflush(stdin);scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;keyi=0;if(G.kind=DG)printf(請輸入?。ㄈ鏏B,其中AB與BA是不同的?。簄);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=UDG)printf(請輸入弧（如AB,其中AB與BA是不同的?。簄);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=DN)printf(請輸入依次輸入弧以及這條弧的權(quán)值（如AB 8,其中AB與BA是不同的?。簄); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; if(G.kind=UDN)printf(請輸入依次輸入弧以及這條弧的權(quán)值（如AB 8,其中AB與BA是不同的弧）：n); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; return OK; /創(chuàng)建鄰接表int FirstAdjVex(ALGraph G,int v)if(G.verticesv.firstarc)return G.verticesv.firstarc-adjvex;return 0;int NextAdjVex(ALGraph G,int v,int w)AList s;s=G.verticesv.firstarc;while(s-adjvex!=w)s=s-nextarc;if(s-nextarc)return s-nextarc-adjvex;return 0;void DFS(ALGraph G,int v)int w;visitedv=1; printf(%c ,G.verticesv);for(w=FirstAdjVex(G,v);w=1;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w); void DFSTraverse(ALGraph G)int v;visited0=1;for(v=1;v=G.vexnum;v+) visitedv=0;for(v=1;v=G.vexnum;v+)if(!visitedv) DFS(G,v); /圖的深度遍歷void BFSTraverse(ALGraph G)int v,w,u;LinkQueue Q;for(v=1;v=G.vexnum;v+) visitedv=0;visited0=1;InitQueue(Q);for(v=1;v=1;w=NextAdjVex(G,u,w) if(!visitedw)visitedw=1; printf(%c ,G.verticesw);EnQueue(Q,w); else break; /圖的廣度遍歷void FindInDegree(ALGraph G,int in)int i,j,k;AList p;for(k=1;k=G.vexnum;k+) ink=0;for(i=1;iadjvex;inj+;p=p-nextarc; /計(jì)算各頂點(diǎn)入度 int TopologicalSort(ALGraph G)int i,k,count;AList p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);if(count=G.vexnum) return ERROR;else return OK; /拓?fù)渑判騣nt Minimum(MGraph G,closedges m)int i,j,min=INFINITY;for(i=1;i=G.vexnum;i+)if(mi.lowcost)if(mi.lowcostmin)min=mi.lowcost;j=i; return j;void MinSpanTree_PRIM(MGraph G,char u)int i,j,k;closedges closedge;k=LocateVex(G,u);for(j=1;j=G.vexnum;j+)if(j!=k) closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=2;i=G.vexnum;i+)k=Minimum(G,closedge);printf(%c%c ,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=1;j=G.vexnum;j+)if(G.arcs