數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告-圖的算法實現(xiàn)-資料下載頁
2025-08-24 17:31本頁面
【導(dǎo)讀】將圖的信息建立文件；姆，克魯斯卡爾和狄克斯特拉三種算法分別實現(xiàn)。//若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。printf;//頂點的信息會出現(xiàn)在矩陣邊界上。
【正文】 for(i=0。i。i++) { for(j=0。j。j++) { if([i][j]==0) [i][j]=9999。 } } for(i=0。i。i++) { dist[i]=[v][i]。 s[i]=0。 if([v][i]9999) path[i]=v。 else path[i]=1。 } s[v]=1。 path[v]=0。 for(i=0。i。i++) { mindis=9999。 for(j=0。j。j++) { if(s[j]==0amp。amp。dist[j]mindis) { u=j。 mindis=dist[j]。 } } s[u]=1。 for(j=0。j。j++) { if(s[j]==0) { if([u][j]9999amp。amp。dist[u]+[u][j]dist[j]amp。amp。dist[u]!=0) { dist[j]=dist[u]+[u][j]。 path[j]=u。 } } } } Dispath(dist,path,s,v)。 } int flag_1。 void Undigraph() { while(1) { system(cls)。 if(flag_1==0) { printf(\n\t\t 提示：若無文件請先輸入數(shù)據(jù)建 立無向圖的鄰接矩陣！ \n)。 system(pause)。 } } } int Search(int front[],int v) { int t。 t=v。 while(front[t]0) t=front[t]。 return t。 } void Kruskal(edgetype edges[],int n) { int front[100]。 int i,vf1,vf2。 printf(用 Kruskal 算法生成的最小生成樹為： \n)。 for(i=0。in。i++) front[i]=0。 for(i=0。in1。i++) { vf1=Search(front,edges[i].w1)。 vf2=Search(front,edges[i].w2)。 if(vf1!=vf2) { front[vf2]=vf1。 printf((%c%c)\n,edges[i].w1,edges[i].w2)。 } } } void main() { int a,i。 printf(\t\t*************圖的實現(xiàn)算法 *****************\n)。 printf(\t\t****************************************\n\n)。 printf(\t\t\t1:建立圖的鄰接矩陣 \n\n)。 printf(\t\t\t2:用 prim 算法生成的最小生成樹為： \n\n)。 printf(\t\t\t3:用 Dijkstra 生成的最短路徑 \n\n)。 printf(\t\t\t4:用 Kruskal 算法生成的最小生成樹為： \n\n)。 printf(\t\t\t5:返回 \n\n)。 printf(\t\t****************************************\n)。 printf(\t\t****************************************\n)。 printf(\n\t\t輸入一個有效的數(shù)字 ,選擇你要做的操作 :\n)。 system(color A)。/*改變界面顏色的，對程序沒什么影響 */ scanf(%d,amp。a)。 switch(a) { case 1: system(cls)。 printf(輸入數(shù)據(jù)建立無向圖的鄰接矩陣 )。 getin_1()。 printf(數(shù)據(jù)保存成功！ \n)。 /*flag_1=1。 Undigraph()。*/ main()。 break。 case 2: getout_1()。 outmatrix()。 MiniSpanTree_PRIM([0])。//用 prim 算法求最小生 成樹 main()。 break。 case 3: getout_1()。 outmatrix()。 printf(\n 采用 Dijkstra 算法得到的最短路徑為： \n)。 for(i=0。i。i++) Dijkstra(i)。 printf(\n)。 main()。 break。 case 5: main()。 case 4: getout_1()。 outmatrix()。 printf(\n)。 edgetype edgex[1000]。 int p,q,c=0。 for(p=0。p。p++) for(q=p+1。q=。q++) { edgex[c++].Cost=[p][q]。 edgex[c].w1=[p]。 edgex[c++].w2=[q]。 } Kruskal(edgex,)。 main()。 break。 } }
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1