【文章內(nèi)容簡介】 m++。 } else if(t==3) {vpvisited[we[i].y1]=1。 vpposition[we[i].y1]=vpposition[we[i].z1]。 for(j=0。j(Gn)。j++) if(vpvvpp[vpposition[we[i].z1]1][j]==0) {vpvvpp[vpposition[we[i].z1]1][j]=we[i].y。 break。 } vpvvpp[we[i].y1][0]=0。 [k++]=wv[we[i].y1]。 [m].info=we[i].info。 [m].z=we[i].z。 [m].y=we[i].y。 m++。 } }printf(Please output the information:\n)。for(i=0。i(Gn)1。i++)printf((%c,%c)\n,[i].z+64,[i].y+64)。}void Create_WLGraph(ALGraph *G){int i,j,t,m,k=0。 EdgeNode *s,*p。 WGraph *W。 W=(WGraph *)malloc(sizeof(WGraph))。 Wv[0]=Gadjlist[0].vertex。 s=Gadjlist[0].firstedge。 while(s!=NULL) {We[k].z=1。 We[k].y=sadjvex。 We[k].info=sinfo。 k++。 s=snext。 } for(i=1。i(Gn)。i++) {Wv[i]=Gadjlist[i].vertex。 s=Gadjlist[i].firstedge。 while(s!=NULL) {m=Panduan_Vertex(k,i,W,s)。 if(m==1) {s=snext。 continue。} else { We[k].z=i+1。 We[k].y=sadjvex。 We[k].info=sinfo。 k++。 s=snext。 } } }/* printf(Please output the information:\n)。 for(i=0。iGn。i++) printf(%c\n,Wv[i])。 for(i=0。iGe。i++) printf(%d,%d,%.1f\n,We[i].z,We[i].y,We[i].info)。*/ select_info(W,G)。 Create_TLGraph(W,G)。}4. 主函數(shù)的偽碼：main(){ALGraph *G。 G=(ALGraph *)malloc(sizeof(ALGraph))。 Create_ALGraph(G)。 Create_WLGraph(G)。}：五．調(diào)試分析：在剛開始寫程序時，由于考慮不全面，在去除連通圖閉合回路的算法中遇到很大困難，后來采用以下方法解決了這個問題：將每個頂點分別放在一個結構體中，結構體中的數(shù)組visited[i]記錄頂點Vi是否被訪問過的情況，position[i]記錄頂點Vi的具體位置，二維數(shù)組vvpp[i][j]記錄已經(jīng)將以該頂點為左頂點或右頂點的權值存入T中后，該權值的右頂點或左頂點的編號。其具體思想是：只要將一個權值存入T中，就將相應的左右頂點放到同一個二維數(shù)組中，之后每欲將一個權值加入T中，先檢驗該權值的兩頂點是否在同一個二維數(shù)組中。若不在，則將該權值存入T中；若在，將該權值舍去（因為再將該權值加入T中，就會出現(xiàn)回路）。2. 方法優(yōu)缺點分析：優(yōu)點：①思想比較簡單，容易令人理解； ②在寫核心算法時，先將字母頂點用相應的數(shù)字代替，所以在將數(shù)字轉(zhuǎn)化成字母回去時，利用數(shù)字與ASCII碼值的固定差值，可以保證用戶在輸入時的大小寫字母都可以被該程序識別。缺點：由于采用數(shù)字來代替字母，中間的轉(zhuǎn)換關系比較復雜，尤其是將對應關系理清需要足夠的耐心和細心。3．主要算法的時間和空間復雜度分析：（1）由于Create_ALGraph( )算法中將讀入頂點的操作執(zhí)行了n次，讀入邊的操作執(zhí)行了2m次，故其時間復雜度為O（n+2m）；（2）由于Create_WLGraph( )算法將讀入權值及其左右頂點的操作執(zhí)行了n次，故其時間復雜度為O（n）；（3）由于Create_TLGraph( )算法中根據(jù)判斷是否構成回路來取舍邊，因為有n條邊，故要執(zhí)行n次，所以時間復雜度是O（n）；（4）由于select_info( )函數(shù)采用簡單選擇法排序，時間復雜度是O（）；（5）所有算法的空間復雜度都是O（1）。六．使用說明程序運行后，用戶根據(jù)提示輸入頂點數(shù)，邊數(shù)，頂點信息，邊的信息，權值，輸入完畢后程序會自動以頂點對（i, j）的形式輸出最小生成樹的邊。七．調(diào)試結果輸入數(shù)據(jù)：“9”，“15”，“ABCDEFGHI”，“A,B”，“”，“A,C”，“”，“A,H”，“”，“A,I”，“”，“B,A”，“”，“B,C”，“”，“C,A”，“”，“C,B”，“”，“C,D”，“”，“C,E”，“”，“C,G”，“”，“D,C”，“”，“D,E”，“”，“D,F”，“”，“E,C”，“”，“E,D”，“”，“E,F”，“”，“E,G”，“”，“F,D”，“”，“F,E”，“”，“F,I”，“”，“G,C”，“”，“G,E”，“”，“G,H”，“”，“H,A”，“”，“H,G”，“”，“H,I”，“”，“I,A”，“”，“I,F”，“”，“I,H”，“”。(雙引號不需輸入)輸出數(shù)據(jù)：(B,C),(H,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I) 運行結果截屏： 八．附錄源程序清單：include /*調(diào)用的頭文件庫說明*/includedefine MaxVerNum 100static void forcefloat(float *p){float f = *p。 /*由于我的TC中不支持浮點數(shù)，故添加了這個程序段*/forcefloat(amp。f)。}typedef struct node /*構造鄰接表的結構體*/{ int adjvex。 float info。 /*存放權值*/ struct node *next。 /*指向下一個鄰接點的指針域*/}EdgeNode。typedef struct vnode /*構造頂點表的結構體*/{ char vertex。 /*頂點域*/ EdgeNode *firstedge。 /*邊表頭指針*/}VertexNode。typedef VertexNode AdjList[MaxVerNum]。typedef struct /*構造圖的結構體*/ {AdjList adjlist。 /*鄰接表*/ int n,e。 /*頂點數(shù)和邊數(shù)*/ }ALGraph。struct bian