最小生成樹演算法的設計與實現
一、實驗目的
1、根據演算法設計需要, 掌握連通網的靈活表示方法;
2、掌握最小生成樹演算法，如prim、kruskal演算法;
3、基本掌握貪心演算法的一般設計方法;
4、進一步掌握集合的表示與操作演算法的應用.
二、預習與參考
1、認真閱讀演算法設計教材和資料結構教材內容, 熟習連通網的不同表示方法和最小生成樹演算法;
2、設計kruskal演算法實驗程式.
[參考資料型別或變數]
typedef nodenumber int; /* 節點編號 */
typedef costtype int; /* 成本值型別 */
typedef elemtype nodenumber /* 實型或任意其它元素型別 */
typedef struct node;
typedef struct edge;
node set=,…,}; /* 節點集, n為連通網的節點數 */
edge es[ ]=,…,}; /* 邊集, m為連通網的邊數 */
edge st[n-1]; /* 最小生成樹的邊集 */
[參考子程式介面與功能描述]
int find(node *set, elemtype elem)
功能: 在陣列set中順序查詢元素elem, 如果不成功, 返回-1; 否則, 使用帶壓縮規則的查詢演算法,返回所在子集的根節點索引.
int union(node *set, elemtype elem1, elemtype elem2)
功能: 應用find演算法首先找到elem1和elem2所在的子集, 然後應用帶加權規則的並運算演算法合併兩個子集. 不成功時, 返回-1; 否則, 返回並集的根節點索引.
void sort(edge *es, int n)
功能: 用任意分類演算法將連通圖的邊集按成本值的非降次序分類.
void kruskal(edge *es, int m, node *set, int n, edge *st)
功能: 對有n個節點, m條邊的連通網, 應用kruskal演算法生成最小生成樹, 最小生成樹的邊儲存在陣列st中.
void output(edge *st, int n)
功能: 輸出最小生成樹的各條邊.
三、實驗要求
上機實驗時，一人一組，獨立上機。
有n個城市可以用（n-1）條路將它們連通，求最小總路程的和。
四、實驗步驟
1、設計測試問題,修改並除錯程式, 輸出最小生成樹的各條邊, 直至正確為止;
2、待各功能子程式除錯完畢, 去掉測試程式, 將你的程式整理成功能模組存檔備用.
五、測試
input:
61 2 6
1 3 1
1 4 5
2 3 5
2 5 6
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
0 0 0
putout:
18六、實驗報告要求
1、闡述實驗目的和實驗內容;
2、闡述kruskal演算法的原理方法;
3、提交實驗程式的功能模組;
4、提供測試資料和相應的最小生成樹。
七、思考題
1、設計由連通網初始邊集陣列生成最小堆的演算法;
2、設計輸出堆頂元素, 並將剩餘元素調整成最小堆的演算法;
3、針對連通網初始邊集最小堆表示, 設計kruskal演算法;
4、採用成本鄰接矩陣表示連通網時, 在剩餘邊中如何實現最小成本邊的查詢?
採用成本鄰接矩陣表示連通網時, 用c語言實現prim演算法.
最小生成樹普里姆演算法的實現
資料結構課程設計 設計說明書 數學與電腦科學學院 2013年3月15日 課程設計任務書 2012 2013學年第二學期 設計內容 圖論中，對於個帶權的連通圖，其每個生成樹所有邊上的權值之和可能不同，把其所有邊上權值之和最小的生成樹稱為圖的最小生成樹。通訊線路鋪設造價最優問題就是最小生成樹的實際應用 ...
演算法設計與分析 貪心法求最小生成樹
一 問題描述 1.可以用連通網來表示n個城市間可能設定的通訊網路，其中網的頂點表示城市，邊表示兩城市之間的路線，邊的權值表示相應的費用。對於n個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是乙個通訊網。現在，我們要選擇這樣一棵生成樹，它使總的費用最少，這棵樹就是最小生成樹。一棵生成樹的費...
資料結構課程設計報告 最小生成樹完整版
課程設計報告 課程名稱 設計題目 學生班級 學生姓名 指導教師 完成日期 資料結構最小生成樹的應用 09 計科 2 班蔣家權，陳相財，吳繼偉，梁麗春林麗惠 2011 1 19 計算機系課程設計報告 課程設計專案研究報告 目錄一 問題分析和任務定義1 二 實現本程式需要解決的問題如下1 三 測試資料2...