【文章內(nèi)容簡介】 adjvex。 int index=LocateVex(g,adj)。 if(vis[index]==0) { cur_pathvertex[cur_pathcount++]=index。 cur_pathvalue+=nodeinfo。 vis[index]=1。 dfs_path(g,src,index,vis,cur_path,min_path)。 cur_pathcount。 cur_pathvalue=nodeinfo。結(jié)束判斷vp是否存在弧頭頂點數(shù)據(jù)元素=LocateVexx(g,adj)最小生成樹權(quán)值加遞歸開始把頂點的值vp復制給adj把鄰接表數(shù)組的頭指針賦值給node用循環(huán)結(jié)構(gòu)復制cur_pat的內(nèi)存到min_path判斷鄰接表指針是否為空node指向下一個結(jié)點 vis[index]=0。 } }} Y N N Yvoid best_path(ALGraph *g,int src){ int vis[MAXVEX]。 memset(vis,0,sizeof(vis))。 GPath cur_path,min_path。 memset(amp。cur_path,0,sizeof(GPath))。/*將cur_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設(shè)置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向cur_path的指針。*/ memset(amp。min_path,0,sizeof(GPath))。/*將min_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設(shè)置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向min_path的指針。*/ =INFINITY。 dfs_path(g,src,src,vis,amp。cur_path,amp。min_path)。 if(!=INFINITY) { int i=0。 printf(\n最佳旅游路線景點下標值是:\n)。 for(i=0。 i。 i++) { printf(%d ,[i])。 } printf(\n)。 printf(\n最佳旅游路線景點是:\n)。 for(i=0。 i。 i++) { printf(%c ,gAdjList[[i]].data)。 } printf(\n)。 }else { printf(建立的圖中沒有最佳路徑\n)。 }}主函數(shù)void main(){ int n, opse,v0,i。 int distance[MAXVEX],pre[2*MAXVEX],path[MAXVEX]。 ALGraph *G。 MGraph *M。 do { printf(\n\n請選擇對圖的操作要求:\n\n)。 for (n=0。 n=30。 n++) printf(* )。 printf(\n* )。 printf(1建立圖的鄰接矩陣 )。 printf( 2圖的鄰接矩陣的輸出 )。 printf( *\n)。 printf(\n* )。 printf(3圖的鄰接鏈表的輸出 )。 printf( 4相鄰景點查詢 )。 printf( *\n)。 printf(\n* )。 printf(5 從某點出發(fā)到另外所有點最短簡單路徑及距離 )。 printf( *\n)。 printf(\n* )。 printf(6 兩個景點之間的最短距離(下標值) )。 printf( *\n)。 printf(\n* )。 printf(7 最佳路徑 )。 printf(8 退出 )。 printf( *\n)。 for (n=0。 n=30。 n++) printf(* )。 printf(\n\n)。 do { scanf(%d,amp。opse)。 }while (opse1||opse8)。 switch (opse) { case 1: { M=(MGraph *)malloc(sizeof(MGraph)) 。 M=create_graph() 。 printf(\n\n)。 break 。 } case 2: { printf(\n您所建立的圖是：\n) 。 output_graphic(M) 。 break 。 } case 3: { printf( 圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:\n)。 G = MGraphToALGraph(M,G)。 output_graphic_c(M,G)。 break 。 } case 4: { printf(\n相鄰景點是：\n) 。 output_Find_ALGraph(G)。 break 。 } case 5: { printf(\n最短簡單路徑及距離是：\n) 。 scanf( %d,amp。v0)。 Dijkstra _One(G,M,v0,distance,pre)。 break 。 } case 6: { printf(兩個景點之間的最短距離(下標值):)。 scanf( %d,amp。v0)。 Dijkstra _Two(G,M,v0,distance,pre)。 break。 } case 7: { printf(最佳路徑(下標值):)。 Dijkstra(M,0,distance,path)。 printf(從結(jié)點%c到其他各結(jié)點的最短距離為:\n,Mvexs[0])。 for(i=1。iMvexnum。i++) printf(到結(jié)點%c的最短距離為%d:\n,Mvexs[i],distance[i])。 printf(從結(jié)點%c到其他各結(jié)點最短路徑的前一結(jié)點為:\n,Mvexs[0])。 for(i=1。iMvexnum。i++) if(path[i]!=1) printf(到結(jié)點%c的前一結(jié)點為%c:\n,Mvexs[i],Mvexs[path[i]])。 break。 } } } while(opse!=8)。}開始請選擇對圖的操作要求n=30？菜單輸出*n=0n++調(diào)用create_graph()，建立圖breakbreakbreak調(diào)用MGraphToALGraph()，把鄰接矩陣轉(zhuǎn)換為鄰接鏈表調(diào)用output_graphic()鄰接矩陣的輸出調(diào)用output_graphic_c()鄰接矩陣的輸出 ……… ………結(jié)束調(diào)用output_Find_ALGraph()輸出相鄰景點breakbreak調(diào)用dijkshort_Two（）函數(shù)，查找兩個景點間的最短距離調(diào)用dijkshort_One（）函數(shù)，查找最短簡單路徑和距離breakbreak調(diào)用Dijkstra（）函數(shù)，查找最佳路徑4 每個題目都必須有運行時的輸入數(shù)據(jù)（隨機產(chǎn)生的數(shù)據(jù)要求輸出顯示），運行的輸出結(jié)果。建立鄰接矩陣：鄰接矩陣輸出：鄰接鏈表輸出：相鄰景點查詢：從某點出發(fā)到另外所有點最短簡單路徑及距離：兩個景點之間的最短距離：最佳路徑：5 每個函數(shù)中應給出盡可能詳細的中文注釋。（源程序全）include include include define INFINITY 32767 /* 最大值∞ *//* 根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù) */define MAXVEX 30 /* 最大頂點數(shù)目 *///鄰接矩陣結(jié)構(gòu)體typedef struct { char vex1, vex2 。 /* 弧或邊所依附的兩個頂點 */int ArcVal 。 /* 弧或邊的權(quán)值 */}ArcType 。 /* 弧或邊的結(jié)構(gòu)定義 */typedef struct{ int vexnum, arum 。 /* 圖的當前頂點數(shù)和弧數(shù) */ char vexs[MAXVEX] 。 /* 頂點向量 */ int adj[MAXVEX][MAXVEX]。}MGraph 。 /* 圖的結(jié)構(gòu)定義 */typedef struct Path{ int vertex[MAXVEX]。 int value。 int count。}GPath。//鄰接鏈表結(jié)構(gòu)體typedef struct ANode { //弧的結(jié)點結(jié)構(gòu)類型 int adjvex。 // 鄰接點在頭結(jié)點數(shù)組中的位置(下標) int info。 //該弧的相關(guān)信息,這里用于存放權(quán)值 struct ANode *nextarc。 //指向下一條弧的指針} ArcNode。typedef struct Vnode //鄰接表頭結(jié)點的類型{ char data。 //頂點信息 ArcNode *firstarc。 //指向第一條弧} VNode。typedef struct { VNode AdjList[MAXVEX]。 //鄰接表數(shù)組 int vexnum,arum。 //圖中頂點數(shù)n和邊數(shù)e} ALGraph。 //圖的鄰接表類型MGraph *Init_MGraph()/* 圖的初始化 */{ MGraph *G。 G=(MGraph *)malloc(sizeof(MGraph)) 。 Gvexnum=0 。 Garum=0 。 /* 初始化頂點數(shù)、邊數(shù) */ return(G) 。 }ALGraph