最小生成樹課程設(shè)計(jì)

1、湖南人文科技學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系課程設(shè)計(jì)說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu) 課 程 代 碼: 408024 題 目: 最小生成樹問題 年級(jí)/專業(yè)/班: 08 級(jí)計(jì)算機(jī)科學(xué)與技術(shù)一班 學(xué) 生 姓 名: 肖禁 吳廣 劉聰 邱建標(biāo) 胡子龍 學(xué) 號(hào):

2、 08408110 0840807 08408109 08408106 08408108 指 導(dǎo) 教 師: 袁 輝 勇 開 題 時(shí) 間: 2009 年 12 月 23 日完 成 時(shí) 間: 2010 年 1 月 1 日摘 要最小生成樹是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應(yīng)用，在圖中對(duì)于 n 個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，最小生成樹就

3、是在所有生成樹中總的代價(jià)最小的生成樹。本課程設(shè)計(jì)是以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu),分別采用 Prim 和 Kruskal 算法求最小生成樹。Kruskal 算法和 Prim 算法是求最小生成樹的常用算法它們分別適用于稠密圖和稀疏圖。最小生成樹的應(yīng)用非常的廣，如礦井通風(fēng)設(shè)計(jì)和改造最優(yōu)化方面以及如何搭建最短的網(wǎng)絡(luò)線纜, 構(gòu)建造價(jià)最低的通訊網(wǎng)絡(luò) 。關(guān)鍵詞： 關(guān)鍵詞：最小生成樹；Kruskal算法；Prim算法Abstract The minimu

4、m Cost spanning tree data structure is an important application of Chinese, in the picture for n vertex even TongWang can create many different spanning tree, minimum spanning tree is in all spanning tree in the total co

5、st of the minimum spanning tree. This course is designed as a figure of the adjacency matrix storage structure, we adopt Prim and Kruskal minimum spanning tree algorithm. Kruskal Prim algorithm and minimum spanning tree

6、algorithm is used for the algorithm respectively applicable and sparsely populated. Minimum spanning tree is very wide application in mines, such as the ventilation design and modification and optimization in how to set