數據結構管道鋪設施工的最佳方案(10頁).doc
下載文檔
上傳人:正***
編號:441473
2022-07-11
9頁
354.50KB
1、 N(N10)個居民之間需要鋪設煤氣管道。假設任意兩個居民之間都可以鋪設煤氣管道,但代價不同。事先將任意兩個居民之間鋪設煤氣管道的代價存入磁盤文件中。設計一個最佳方案使得這N個居民之間鋪設煤氣管道所需代價最少,并希望以圖形方式在屏幕上輸出結果。二、需求分析在N(N10)個居民區之間鋪設煤氣管道所需代價最小,即求最小生成樹問題。在我們的課本中介紹了兩種求解方法:普利姆算法和克魯斯卡爾算法。普利姆算法與網的變數無關,適宜求解邊稠密的網的最小生成樹。而克魯斯卡爾算法正好相反,適宜求解邊稀疏的最小生成樹。由于在實際問題中,居民數量一般很有限,而任何兩個居民區都可能有連線,即這樣的圖應該是邊較為稠密的。2、因此,我們選擇了普利姆算法對問題進行求解。三、總體設計普利姆算法的思想是:從連通網N=V,E中的某一頂點U0出發,選擇與它關聯的具有最小權值的邊(U0,v),將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中,而另一個頂點不在U中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續下去,直到網中的所有頂點都加入到生成樹頂點集合U中為止。根據對模型的功能分析,該管道鋪設設計應有以下模塊:1、 管道鋪設信息的輸入2、 最小生成樹信息的輸出管道鋪設問題功能模塊圖:建立最小生成樹并輸出信息輸入模塊最小生成樹問題 四、詳細設計 1、類定義:class edgeset /定3、義一條生成樹的邊邊public:int fromvex; /邊的起點int endvex; /邊的終點int weight; /邊的權值;class graphpublic:int w;int vn+1; /存放頂點int an+1n+1; /鄰接矩陣edgeset ctn+1; /最小生成樹的邊集 void create(graph &g);/建立鄰接矩陣void print(graph g); /輸出鄰接矩陣void dfs(graph g,int i); /深度優先遍歷void prim(graph &g); /普利姆算法;2、類的成員函數的實現void graph:create(gra4、ph &g)int i,j,k; cout請輸入n居民點信息:; for(k=1;kg.vk; /輸入居民點信息for(i=1;i=n;i+)for(j=1;j=n;j+) if(i=j)g.aij=0; else g.aij=9999; /9999代表無窮 coutendl;for(k=1;k=e;k+) /輸入一條邊(i,j)的代價wcoutijw;g.aij=w;g.aji=w;void graph:print(graph g)for(int i=1;i=n;i+)for(int j=1;j=n;j+)couti到j代價為:g.aijendl; coutendl;void graph:d5、fs(graph g,int i)int j;coutg.vi ;visitedi=true; /標記表示已被訪問過for(j=1;j=n;j+)if(g.aij!=9999)&(g.aij!=0)&(!visitedj)dfs(g,j);void graph:prim(graph &g)int i,j,k,min,g1,m,w;for(i=1;in;i+) /從頂點1出發求最小生成樹的邊g.cti.fromvex=1;g.cti.endvex=i+1;g.cti.weight=g.a1i+1;for(k=2;k=n;k+)min=9999;m=k-1;for(j=k-1;jn;j+) /找權6、值最小的樹邊if(g.ctj.weightmin)min=g.ctj.weight;m=j;edgeset temp=g.ctk-1;g.ctk-1=g.ctm;g.ctm=temp;j=g.ctk-1.endvex;for(i=k;in;i+)g1=g.cti.endvex;w=g.ajg1;if(wg.cti.weight)g.cti.weight=w;g.cti.fromvex=j;3、主函數mainvoid main()int i,j,m;graph g;cout*輸入信息*endl; g.create(g); /建立網的鄰接矩陣cout*輸出信息*endl; g.print(g);c7、out*普利姆算法求最小生成樹*endl;g.prim(g);/用普利姆算法求最小生成樹for(i=1;in;i+)coutg.cti.fromvex ;coutg.cti.endvex ;coutg.cti.weightendl; cout*深度優先遍歷*endl;coutm;coutendl;cout已訪問居民點:; g.dfs(g,m); coutendl;五、程序調過程CreateMainPrintPrimDfs六、程序測試六、總結通過數據結構的課程設計使我們對所學的知識有了更好的理解,也增強了大家的動手能力。同時也發現了自己的很多不足之處,對知識的應用能力很是欠缺,應用軟件的能力及編程水平與課程要求更是存在很大的差距。程序的運行結果與理論推導結果吻合,即該算法與程序設計滿足課程設計要求。該程序的主要優點是簡單易懂,不存在理解上的障礙,也很自然地想到這種解法。主要缺點是程序的變動性比較差,類中沒有私有成員,都以公有定義!