版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
算法導(dǎo)論4.6最小生成樹(shù)程勝計(jì)科13-04班問(wèn)題簡(jiǎn)介網(wǎng)絡(luò)G=(V,E)是一個(gè)無(wú)向連通帶權(quán)圖,E中每一條邊(v,w)的權(quán)為c[v][w]。如果G的一個(gè)子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù),則稱(chēng)G’為G的生成樹(shù)。在G的所有生成樹(shù)中,各邊權(quán)之和最小的稱(chēng)為G的最小生成樹(shù)。Prim算法設(shè)G=(V,E)是連通帶權(quán)圖,V={1,2,….n}.算法的基本思想是:首先置S={1},然后只要S是V的真子集,就做如下貪心選擇:遍歷滿(mǎn)足i∈
S,j∈
V-S的點(diǎn),找出c[i][j]最小的邊,將頂點(diǎn)加入S中。此過(guò)程一直進(jìn)行到S=V為止,所選取的邊構(gòu)成的就是G的最小生成樹(shù)。void
prim(int
n,
Type**c)
{
Typelowcost[MAX];
int
clost[max];
bools[max];s[1]=true;
for
(i
=
2;
i
<=
n;
i++)
{
lowcost[i]
=
c[1][i];
clost[i]
=
1;
s[i]=false;
}
for
(i
=
1;
i
<n;
i++)
{
Typemin
=
inf;
intj=1;
for
(intk=
2;
k<=
n;
k++)
{
if
(lowcost[k]
<
min
&&
!s[k])
{
min
=
lowcost[k]
j=k;
}
}
cout
<<
“j"
<<
’’<<
closet[j]
<<
endl;
s[j]=true;
for
(intk=
2;
k<=
n;
k++)
{
if
(c[j][k]
<
lowcost[j])
&&(!s[k])
{
lowcost[k]
=
c[j][k];
closet[k]=j;
}
}
}
初始化遍歷鄰近點(diǎn),找出最短距離的邊,輸出點(diǎn)和邊,并放入S。對(duì)于新加入S的點(diǎn),通過(guò)比較最短距離,更新lowcost數(shù)組算法過(guò)程詳解算法的核心在兩個(gè)數(shù)組:closet和lowcost。對(duì)于j∈
V-S,closet[j]表示點(diǎn)j與所有S中點(diǎn)的連線(xiàn)中最短的連接點(diǎn)。而lowcost[j]的值就是c[j][closet[j]].在算法的執(zhí)行過(guò)程中,先找出V-S中是lowcost值最小的點(diǎn),選取邊(j,closet[j]),將j添加到S中,然后根據(jù)與新加入S的點(diǎn)的距離的比較,更新lowcost數(shù)組。一.初始化在Prim算法中,最小生成樹(shù)的起點(diǎn)設(shè)置為1.此時(shí)S={1},由于S中只含有點(diǎn)1,故此時(shí)lowcost[i]=c[1][i],Closet[i]=1:Lowcoset[1]=0,
Lowcoset[2]=6,Lowcoset[3]=1,Lowcoset[4]=5,Lowcoset[5]=max,Lowcoset[6]=max,(max表示無(wú)直接連線(xiàn))Example1536243255566641153624二.Lowcost第一次循環(huán)
遍歷lowcost數(shù)組,找到最小值為lowcost[3]=1,所以將點(diǎn)3加入S中,選擇的邊為(1,3),此時(shí)S={1,3}1536241536241三.更新lowcost數(shù)組前一步將點(diǎn)3加入S,根據(jù)定義,數(shù)組lowcost和closet可能會(huì)發(fā)生改變,需要比較連接點(diǎn)的距離,決定是否更新數(shù)組。C[3][2]=5<6,更新lowcost[2]=5,closet[2]=3;C[3][3]=0;C[3][4]=5=5,不更新;C[3][5]=6<max,更新lowcost[5]=6,clost[5]=3;C[3][6]=4<max,更新lowcost[6]=4,c;ost[6]=3.1536241四.Lowcost數(shù)組第二次循環(huán)由于上一步lowcost數(shù)組更新,故第二次循環(huán),找出最小值。其中最小值為lowcost[6]=4,將點(diǎn)6添加到S中,此時(shí)S={1,3,6}153624115362414五.Lowcost更新由于新加入點(diǎn)6,根據(jù)定義,數(shù)組lowcost和closet可能會(huì)發(fā)生改變,需要比較連接點(diǎn)的距離,決定是否更新數(shù)組:C[6][2]=max,不更新;C[6][3]=4>1,不更新;C[6][4]=2<5,更新lowcost[4]=2,closet[4]=6;C[6][5]=6=6,不更新;C[6][6]=0,不更新;15362414依此類(lèi)推………153624141536241421536241452
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 工作總結(jié)之護(hù)理實(shí)習(xí)總結(jié)范文
- 工作總結(jié)之單片機(jī)畢業(yè)設(shè)計(jì)總結(jié)
- 銀行員工培訓(xùn)計(jì)劃制度
- 酒店餐飲衛(wèi)生許可證管理及檢查制度
- 《數(shù)字媒體概述》課件
- 酒店實(shí)習(xí)報(bào)告總結(jié)800字(33篇)
- 《保單價(jià)值與準(zhǔn)備金》課件
- 《記憶效果研究》課件
- 2024屆高考語(yǔ)文一輪復(fù)習(xí)第1章信息類(lèi)文本閱讀6第五節(jié)分析文本論證課件
- 女裝款式設(shè)計(jì)-第四章 禮服設(shè)計(jì)
- 六年級(jí)書(shū)法上冊(cè)電子教案設(shè)計(jì)
- 2024年軍隊(duì)文職統(tǒng)一考試《專(zhuān)業(yè)科目》管理學(xué)試卷(網(wǎng)友回憶版)含解析
- DB13-T 5863-2023 造血干細(xì)胞移植病區(qū)醫(yī)院感染預(yù)防與控制規(guī)范
- GB/T 44456-2024電子競(jìng)技場(chǎng)館運(yùn)營(yíng)服務(wù)規(guī)范
- 2024年國(guó)家網(wǎng)絡(luò)安全宣傳周科普課件
- 三級(jí)人工智能訓(xùn)練師(高級(jí))職業(yè)技能等級(jí)認(rèn)定考試題庫(kù)-上(單選題部分)
- 初中語(yǔ)文講座:《素養(yǎng)導(dǎo)向初中語(yǔ)文大單元教學(xué)》課件
- 第五單元大單元教學(xué)課件 2024-2025學(xué)年統(tǒng)編版語(yǔ)文七年級(jí)上冊(cè)
- 10.再塑生命的人市公開(kāi)課一等獎(jiǎng)?wù)n件名師大賽獲獎(jiǎng)?wù)n件
- 電批風(fēng)批扭力測(cè)試記錄
- (高清版)WS∕T 389-2024 醫(yī)學(xué)X線(xiàn)檢查操作規(guī)程
評(píng)論
0/150
提交評(píng)論