算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書(編輯修改稿)
2025-03-12 10:07 本頁面
【文章內(nèi)容簡介】 )，它們作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路 11 ，如果對稱的兩點(diǎn)熟人不同的權(quán)值，且同一點(diǎn)輸入權(quán)值在構(gòu)成的最小生成樹中會(huì)產(chǎn)生隨機(jī)數(shù)。無向圖的鄰接矩陣是對稱矩陣。 O(2n) 1. 圖 1為登錄界面 12 圖 1 2. 圖 2為輸入城市信息界面 圖 2 13 3. 圖 3為顯示鄰接矩陣界面 圖 3 4. 圖 4為遍歷所有城市得到最小生成樹界面 圖 4 5. 圖 5為退出界面 圖 5 14 （帶注釋） include include include define max 20//城市間邊數(shù) define MAX_LNT 10 //城市數(shù) define INF 32627 //兩個(gè)城市間無直接路徑，用大數(shù) 32627 表示 typedef struct node /*構(gòu)造一個(gè)結(jié)構(gòu)體，兩個(gè)城市可以看成起點(diǎn)和終點(diǎn)，之間的道路可 以看成一個(gè)邊 */ { int str。 /*起點(diǎn) */ int end。 /*終點(diǎn) */ int dis。/*距離 */ }node。 node p[max],temp。 /*p 記錄城市信息 */ typedef struct{ //鄰接矩陣存儲(chǔ)圖結(jié)構(gòu) int vexs[MAX_LNT]。 //數(shù)組用于存儲(chǔ)城市數(shù) int adj[max+1][max+1]。 //圖的鄰接矩陣表示 int n,e。 //n 代表城市數(shù)， e代表城市間 邊數(shù) }graph。 int pre[100],rank[100]。/*用于判斷是否構(gòu)成回路 */ //int arcs[MAX_LNT][MAX_LNT]。/*n 表示城市個(gè)數(shù)， arcs[][]記錄城市間權(quán)值 */ int menu( ) /*菜單函數(shù) */ { int m。 printf( 求最小生成樹 \n)。 printf( ________________________________\n\n)。 printf( 1 輸入城市之間的信息 \n)。 printf( 2 遍歷所有城市生成最小生成樹 \n)。 printf( 3 退出 \n)。 printf( ________________________________\n\n)。 printf( 請輸入所選功能 13:\n)。 system(color E)。/*改變界面顏色的 */ scanf(%d,amp。m)。 return m。 } 15 void create(graph *g) /*輸入城市信息 */ { int i,j,k。 printf(輸入城市數(shù)為 :)。 scanf(%d,amp。(gn))。 printf(\n)。 printf(輸入個(gè)城市間邊數(shù)為 :)。 scanf(%d,amp。(ge))。 printf(輸入城市的各個(gè)頂點(diǎn)為 :)。 for(i=0。i(gn)。i++) scanf(%d,amp。(gvexs[i]))。 //頂點(diǎn)存入數(shù)組 vexs[] printf(輸入 %d 條邊，建立鄰接矩陣 ,(ge))。 printf(\n)。 for(i=0。i(gn)。i++) //初始化鄰接矩陣 { for(j=0。j(gn)。j++) { if(i==j) gadj[i][j]=0。 else gadj[i][j]=INF。 } } printf(請輸入具有 鄰接關(guān)系的兩個(gè)頂點(diǎn)在矩陣中所在的行與列及權(quán)值 :\n)。 for(k=0。k(ge)。k++) //有 ge 條邊，即有 ge個(gè)權(quán)值 { scanf(%d,%d,amp。i,amp。j)。 scanf(%d,amp。gadj[i][j])。 } for(i=0。i(gn)。i++) for(j=0。j(gn)。j++) gadj[j][i]=gadj[i][j]。 printf( 圖的鄰接矩陣如下 \n)。 for(i=0。i(gn)。i++) //輸出鄰接矩陣 g { for(j=0。j(gn)。j++) if(gadj[i][j]==INF) printf(\t%3s,∞ )。 else 16 printf(\t%3d,gadj[i][j])。 printf(\n)。 } } /*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路 */ void set(int x)/*初始化 */ { pre[x] = x。 rank[x] = 0。 } int find(int x)/*找到這個(gè)點(diǎn)的祖先 */ { if(x != pre[x]) pre[x] = find(pre[x])。 return pre[x]。 } void Union(int x,int y)/*將這兩個(gè)添加到一個(gè)集合里去 */ { x = find(x)。 y = find(y)。 if(rank[x] = rank[y]) { pre[y] = x。 rank[x] ++。 } else pre[y] = x。 } void Kruskal(graph *g ) { int ans = 0,i,j,k = 0。 /*ans 用來記錄生成最小樹的權(quán)總值 */ int index。 int count = 0。 /*記錄打印邊的條數(shù) */ for(i = 0。i(gn)。i ++) /*初始化數(shù)組 pre[x],rank[x]*/ set(i)。 for(i = 0。i(gn)。i ++) { for(j = i + 1。j (gn)。j ++) { p[++k].str = i。 p[k].end = j。 17 p[k].dis = gadj[i][j]。 /*先把所有城市之間的路段看成一個(gè)邊 */ } } for(i=0。ik。i++) /*把所有的邊按從小到大進(jìn)行排序 */ { index=i。 for(j=i+1。j=k。j++) if(p[j].dis p[index].dis) index=j。 temp=p[index]。 p[index]=p[i]。 p[i]=temp。 } for(i = 0。i k。i ++) { if(find(p[i].str) != find(p[i].end))/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則執(zhí)行下面操作 */ { printf(\t 第 %d 條路段為： %d%d, 權(quán)值為 %d\n,++ count,p[i].str,p[i].end,p[i].dis)。/*將這條邊的起點(diǎn)、終點(diǎn)打印出來 */ ans += p[i].dis。 /*說明這條路段要用 */ Union(p[i].str,p[i].end)。 } } printf(\t 遍歷所有城市得到最小生成樹的代價(jià)為 : %d\n\n,ans)。
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1