最小生成樹問題的算法實現(xiàn)及復(fù)雜度分析—天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院(算法設(shè)計與分析-全文預(yù)覽
【正文】 生成樹，每一個生成樹都可以是一個通信網(wǎng)。本設(shè)計以 Visual Studio 2020作為開發(fā)平臺， C/C++語言作為編程語言，以鄰接矩陣作為存儲結(jié)構(gòu)，編程實現(xiàn)了最小生成樹算法?！?天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院 (算法設(shè)計與分析 ) 算法設(shè)計與分析課程設(shè)計報告 學(xué)院計算機科學(xué)與技術(shù) 專業(yè)計算機科學(xué)與技術(shù) 年級 2020 姓名學(xué)號 2020年 5月 19日 題目：最小生成樹問題的算法實現(xiàn)及復(fù)雜度分析 摘要：該程序操作簡單，具有一定的應(yīng)用性。最短路徑的問題在現(xiàn)實生活中應(yīng)用非常廣泛，如郵遞員送信、公路造價等問題。 n個城市之間最多可以設(shè)置n（ n1） /2條線路，那么如何在這些可能的線路中選擇 n1 條使總的代價最小呢？可以用連通網(wǎng)來表示 n 個城市以及 n 個城市之間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩個城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的代價。最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能 是多個，他們之間的權(quán)值之和相等。它的基本思想是：首先選取圖中任意一個頂點 v 作為生成樹的根，之后繼續(xù)往生成樹中添加頂點 w，則在頂點 w 和頂點 v 之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和 v 相鄰接的邊中屬最小。 普里姆算法構(gòu)造最 小生成樹的過程 普里姆（ Prim）算法設(shè)計： 一：定義模塊： 1. 頭文件、新類型及固定值定義。 typedef int VertexType。 typedef int VertexType。 typedef struct { VertexType vexs[MAX_VERTEX_NUM]。 3. 在實現(xiàn)最小生成樹算法時，定義輔助數(shù)組，進行判斷遍歷。 4. 最后生成最小生成樹時，采用輔助數(shù)組進行結(jié)果的記錄。 }result[MAX_VERTEX_NUM]。 for(k=0。//沒有這個頂點 } 2. 無向圖的創(chuàng)建函數(shù)。 VertexType v1,v2。i。 cout 輸出網(wǎng)的 個 頂 點 ( 限數(shù)字 ):endl。 cout建立弧，請輸入 條弧的頂點和權(quán)值(v1,v2,w):endl。 i=LocateVex(G,v1)。 [j][i].adj=[i][j].adj。 //申請數(shù)組 result pax。 // 確 定初 始結(jié) 點 的下 標 for(j=0。 //數(shù)組中的下標起箭頭的作用，即它是邊的第二個尾結(jié)點！ } dge[k].lowcost=0。 // 在 dge數(shù)組中找到最小的一條邊，并返回尾結(jié)點的下標！ coutK 的尋求結(jié)果為 (數(shù)組 dge 中的下標）： kendl。 x=LocateVex(G,dge[k].adjvex)。 dge[k].lowcost=0。 dge[j].adjvex=
法律信息相關(guān)推薦
鄂ICP備17016276號-1