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