資料結構管道鋪設施工的最佳方案

n(n>10)個居民之間需要鋪設煤氣管道。假設任意兩個居民之間都可以鋪設煤氣管道，但代價不同。事先將任意兩個居民之間鋪設煤氣管道的代價存入磁碟檔案中。

設計乙個最佳方案使得這n個居民之間鋪設煤氣管道所需代價最少，並希望以圖形方式在螢幕上輸出結果。

二、需求分析

在n（n>10）個居民區之間鋪設煤氣管道所需代價最小，即求最小生成樹問題。在我們的課本中介紹了兩種求解方法：普利姆演算法和克魯斯卡爾演算法。

普利姆演算法與網的變數無關，適宜求解邊稠密的網的最小生成樹。而克魯斯卡爾演算法正好相反，適宜求解邊稀疏的最小生成樹。

由於在實際問題中，居民數量一般很有限，而任何兩個居民區都可能有連線，

即這樣的圖應該是邊較為稠密的。因此，我們選擇了普利姆演算法對問題進行求解。

三、總體設計

普利姆演算法的思想是：從連通網n=中的某一頂點u0出發，選擇與它關聯的具有最小權值的邊(u0,v)，將其頂點加入到生成樹的頂點集合u中。以後每一步從乙個頂點在u中，而另乙個頂點不在u中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合u中。

如此繼續下去，直到網中的所有頂點都加入到生成樹頂點集合u中為止。

根據對模型的功能分析，該管道鋪設設計應有以下模組：

1、管道鋪設資訊的輸入

2、最小生成樹資訊的輸出

功能模組圖：

四、詳細設計

1、類定義：

class edgeset //定義一條生成樹的邊邊

;class graph

;2、類的成員函式的實現

void graph::create(graph &g)

}void graph::print(graph g)

cout< }

}void graph::dfs(graph g,int i)

void graph::prim(graph &g)

for(k=2;k<=n;k++)

}3、主函式main

void main()

cout《深度優先遍歷< cout<<"輸入開始訪問的居民點：";

cin>>m;

cout< cout<<"已訪問居民點:";

g.dfs(g,m);

cout<}

五、程式調過程

六、程式測試

六、總結

通過資料結構的課程設計使我們對所學的知識有了更好的理解，也增強了大家的動手能力。同時也發現了自己的很多不足之處，對知識的應用能力很是欠缺，應用軟體的能力及程式設計水平與課程要求更是存在很大的差距。

程式的執行結果與理論推導結果吻合，即該演算法與程式設計滿足課程設計要求。該程式的主要優點是簡單易懂，不存在理解上的障礙，也很自然地想到這種解法。主要缺點是程式的變動性比較差，類中沒有私有成員，都以公有定義！