課程設計報告
課程名稱： 設計題目： 學生班級： 學生姓名： 指導教師： 完成日期：
資料結構最小生成樹的應用 09 計科 2 班蔣家權，陳相財，吳繼偉，梁麗春林麗惠 2011-1-19
計算機系課程設計報告
課程設計專案研究報告
目錄一、問題分析和任務定義1 二、實現本程式需要解決的問題如下1 三、測試資料2 四、演算法思想3 五、模組劃分4 六、演算法設計與分析7 七、源程式11 八、測試資料14 九、課程設計專案進度表及任務分配表及任務分配表16 十、設計心得17 十、參考書目
計算機系課程設計報告
一、問題分析和任務定義
在 n 個城市間建立通訊網路，需架設 n-1 條線路。求解如何以最低經濟代價建設此通訊網，這是乙個最小生成樹問題。要求：
（1）利用普利姆演算法求網的最小生成樹； （2）輸出生成樹中各邊及權值。
二、實現本程式需要解決的問題如下
(1)、如何選擇儲存結構去建立乙個帶權網路。 (2)、如何在所選儲存結構下輸出這個帶權網路。 (3)、如何實現 prim 演算法的功能。
(4)、如何從每個頂點開始找到所有的最小生成樹的頂點。 (5)、如何輸出最小生成樹的邊及其權值。 此問題的關鍵在於如何實現 prim 演算法，實現的過程中如何得到構成最小生成樹的所有頂點， 此外輸出也是乙個關鍵問題所在， 在此過程中經過了多次除錯。
首先我們對問題進行大致的概要分析： 這個問題主要牽涉到通過 prim 的基本演算法思想實現程式所要求的功能，該演算法的主要思想是：假設 n=（v，）是連通網，te 是 n 上最小生成樹中邊的集合 。
演算法從 u=( u0∈v),te={} 開始 ， 重複執行下述操作 ： 在所有 u∈u,v∈v-u 的邊（u,v）∈e 中找一條代價最小的邊（u0,v0）併入集合 te，同時 v0 併入 u，直至 u=v 為止。此時 te 中必有 n-1 條邊，則 t=（v，）為 n 的最小生成樹。
問題的輸入資料的格式為：首先提示輸入帶權網路的頂點邊數，我定義的為整形資料型，然後輸入每一條邊的資訊，即邊的兩個頂點以及權值，是十進位制整數型別，這樣我們就建立乙個帶權網路，並用鄰接矩陣來儲存，生成乙個方陣顯示出來。 問題的輸出資料格式為：
輸出是以鄰接矩陣儲存結構下的方陣，以及從不同頂點開始省城的最小生成樹。 題目要求以及達到目標： 題目要求用普利姆演算法實現任意給定的網和頂點的所有最小生成樹，並且輸出各邊的權值。
-1-計算機系課程設計報告
三、測試資料
第一組頂點數（vertices） 、邊數（edge） ：2、1 起始節點（starting） 、下個節點（terminal） 、權值（weights） ：1、2、5 **結果<1,2>5 第二組頂點數（vertices） 、邊數（edge） ：
3、3 起始節點（starting） 、下個節點（terminal） 、權值（weights） ：1、2、4 1、3、5 2、3、6 **結果<1,2>4、<1,3>5 第三組第三組頂點數（vertices） 、邊數（edge） ：4、5 ， 起始節點（starting） 、下個節點（terminal） 、權值（weights） ：
1、2、3 1、3、4 1、4、6 2、4、7 3、4、5
，**結果<1,2>3、<1,3>4、<1,4>6
-2-計算機系課程設計報告
四、演算法思想
prim 演算法求最小生成樹的主要思想此演算法是普利姆與 1957 年提出的一種構造最小生成樹的演算法，主要思想是：假設 n= （v， ） 是連通網， 是 n 上最小生成樹中邊的集合。 te 演算法從 u=( u0 ∈v),te={}開始，重複執行下述操作：
在所有 u∈u,v∈v-u 的邊（u,v）∈e 中找一條代價最小的邊（u0,v0）併入集合 te，同時 v0 併入 u，直至 u=v 為止。 此時 te 中必有 n-1 條邊，則 t=（v，）為 n 的最小生成樹。 對於最小生成樹問題最小生成樹是指在所有生成樹中，邊上權值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權值之和相等。
五、模組劃分
（1）預處理 #include < #include < #define inf 9999 #define max 40 #define linelenght 77 （2）普里姆演算法 void prim(int g[max],int n) /* prim 的函式 */ lowcost[1]=0; /* 標誌頂點 1 加入 u 集合 */ for(i=2;i<=n;i++) /* 形成 n-1 條邊的生成樹 */ （5）建立無向圖 int adjg(int g[max]) /* 建立無向圖 */ for(i=1;i<=n;i++) for(j=1;j<=n;j++) g[i][j]=inf; /* 初始化矩陣，全部元素設為無窮大 */ for(k=1;k<=e;k++) g[v1][v2]=weight; g[v2][v1]=weight; } return(n); } /* 返回節點個數 n */ （6）輸出無向圖的鄰接矩陣 void pri(int g[max],int n) /* 輸出無向圖的鄰接矩陣 */ } printf("\n"); } （7）主函式模組 void main() /* 主函式 */
最小生成樹實驗報告
最小生成樹演算法的設計與實現 一 實驗目的 1 根據演算法設計需要,掌握連通網的靈活表示方法 2 掌握最小生成樹演算法，如prim kruskal演算法 3 基本掌握貪心演算法的一般設計方法 4 進一步掌握集合的表示與操作演算法的應用.二 預習與參考 1 認真閱讀演算法設計教材和資料結構教材內容,熟...
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...
資料結構課程設計報告
課程設計報告 課程名稱資料結構 課題名稱生死者遊戲 專業資訊管理與資訊系統 班級學號 姓名指導教師 2011 年 1 月 20 日 湖南工程學院 課程設計任務書 課程名稱資料結構 課題生死者遊戲 專業班級 學生姓名 學號指導老師 審批任務書下達日期 2011 年 1 月 3 日 任務完成日期 201...