一．問題描述
1.可以用連通網來表示n個城市間可能設定的通訊網路，其中網的頂點表示城市，邊表示兩城市之間的路線，邊的權值表示相應的費用。
對於n個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是乙個通訊網。現在，我們要選擇這樣一棵生成樹，它使總的費用最少，這棵樹就是最小生成樹。一棵生成樹的費用就是樹上各邊的費用之和。
2.本程式的目的是要建設乙個最經濟的通訊網，根據使用者輸入的網，輸出相應的最小生成樹。在這裡城市以及兩城市之間的費用都用整型數來代替。
3．程式執行的命令包括：
（1）利用克魯斯卡爾演算法求最小生成樹。
（2）構造最小生成樹中的連通分量。
（3）權值應存放在定義的陣列中。
（4）輸入城市個數。
（5）輸出費用最少的生成樹。
（6）結束。
4．測試資料
使用者自定義輸入城市個數，輸入結束後回車即顯示生成的最小生成樹及最小開銷。
二．概要設計
1：抽象資料型別mfset的定義：
adt mfset
return 0;
}3：抽象資料型別圖的定義如下：
adt graph
vr=4：抽象資料型別樹的定義如下：
adt tree，h是如下二元關係：
（1）在d中存在唯一的稱為根的資料元素root，它在關係h下無前驅；
（2）若d-≠，則存在d-的乙個劃分d1，d2，…，dm（m>0），對任意j≠k（1≤j,k≤m）有dj∩dk=，且對任意的i（1≤i≤m），惟一存在資料元素xi∈di有∈h；
（3）對應於d-的劃分，h-有惟一的乙個劃分h1，h2，…，hm（m＞0），對任意j≠k(1≤j，k≤m)有hj∩hk=，且對任意i（1≤i≤m），hi是di上的二元關係，（di，）是一棵符合本定義的樹，稱為跟root的子樹。
5:本程式包括兩個模組，呼叫關係比較簡單：
（1）主程式模組
（2）帶權無向圖模組。
程式各模組之間的呼叫關係如下：
三．詳細設計
#include
#include
#include
using namespace std;
#define mod 101
#define maxn 30
int set[maxn];
int rank[maxn];
typedef struct mintree
mintree;
mintree map[maxn], mst[maxn];
bool cmp(const mintree a,const mintree b)
//快排比較函式
void init(int n)
}int find(int x)
//路徑壓縮
return r;
}bool merge(int x, int y)
else if (rank[fx] < rank[fy])
else
return false;
//兩端點原本在乙個集合，返回假。
}int main()
putsn");
sort(map, map + k, cmp);
按邊從小到大的順序進行快速排序
ans = 0;
num = 0;
printf("得到開銷最小的通訊網路如下：\n");
for (i = 0; i
return 0;
}4.除錯分析
1.在本程式中用儲存邊（帶權）的陣列表示圖，而不是用鄰接矩陣的陣列表示法或鄰接表。為了讓讀者能一目了然看清結果，在終端輸出從頂點0開始的最短路徑時，設定了輸出值的寬度。
2.為了簡便起見，程式中的頂點、邊的權值都設定成了整形，頂點的標記從0開始,即用數字代替城市名稱。
3.在寫程式時遇到很多有關專業名詞的c語言編譯，沒有完全套用書上的固有解釋，而是按照自己有限的英語詞彙的理解去編譯的。
4.由於克魯斯卡爾演算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法，構造最小生成樹的時間複雜度為o(eloge)，e為網中邊的數目，所以其時間複雜度與邊有關，它適用於稀疏圖。普里姆演算法也是求最小生成樹的基本演算法，其時間複雜度為o(n)，與網中的邊數無關，而與定點數有關，故其適用於求邊稀疏的網的最小生成樹。
所以說，兩種演算法各有優勢。
5.通過求最小生成樹，進一步掌握了圖的含義，掌握了克魯斯卡爾演算法的基本思想及流程。知道了克魯斯卡爾演算法與普里姆演算法的區別與聯絡。
通過本次課程設計，鍛鍊了我們的實際操作能力，培養了我們嚴密的思維和嚴謹的態度。
演算法設計與分析 1
湖南中醫藥大學 2009 2010 學年第一學期 演算法設計與分析 期末考試試卷 班級姓名學號 一 選擇題 10題 2分 20分 1.我們常用演算法的最壞時間來估計演算法的時間複雜性，下面 不是這樣做的原因 a 在實際問題中，演算法的執行時間常常達到這個上界。b 平均執行時間難以計算。c 假設每乙個...
演算法設計技巧與分析答案
參 第1章演算法分析基本概念 1.1 a 6 b 5 c 6 d 6 1.4演算法執行了7 6 5 4 3 2 1 28次比較 1.5 a 演算法modselectionsort執行的元素賦值的最少次數是0,元素已按非降序排列的時候達到最小值。b 演算法modselectionsort執行的元素賦值...
演算法設計與分析期末試題
總題一 記得哪些演算法複雜性的知識？用自己的話簡述。例如最壞時間複雜性 複雜性漸進性態的階 二 演算法的時間複雜性分析 1 如何根據演算法的結構分析演算法的時間複雜性？例如選擇基本運算步驟 依據演算法的結構統計。2 分析遞迴演算法的方法，歸方程方法和遞迴樹。姐遞迴方程有迭代法 遞推 法解遞迴方程，或...