對(duì)計(jì)算機(jī)考研感興趣的同學(xué)趕緊看過來，這里是小編整理的有關(guān)2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)考點(diǎn)“最小代價(jià)生成樹”的內(nèi)容，快來看看吧！希望能對(duì)大家有所參考。
2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)高頻考點(diǎn)“最小代價(jià)生成樹”
　　無向連通圖的生成樹是一個(gè)極小連通子圖，它包括圖中全部頂點(diǎn)，并且有盡可能少的邊。
　　無向連通網(wǎng)絡(luò)的最小代價(jià)生成樹是所有生成樹中邊的權(quán)值之和最小的。
　　(1)普里姆算法：
　　首先，從n個(gè)頂點(diǎn)中任選一個(gè)頂點(diǎn)v加入到原來為空的生成樹中;然后，重復(fù)執(zhí)行下列操作：從一個(gè)頂點(diǎn)在生成樹中，而另一個(gè)頂點(diǎn)不在生成樹中的那些邊中，選取一條權(quán)值最小的邊，并將這條邊以及它所關(guān)聯(lián)的目前還不在生成樹中的那個(gè)頂點(diǎn)加入到生成樹中。當(dāng)生成樹中的頂點(diǎn)數(shù)達(dá)到n時(shí)，整個(gè)構(gòu)造過程結(jié)束。
　　(2)克魯斯卡爾算法
　　克魯斯卡爾算法是求連通網(wǎng)的最小生成樹的另一種方法。與普里姆算法不同，它的時(shí)間復(fù)雜度為O（eloge）（e為網(wǎng)中的邊數(shù)），所以，適合于求邊稀疏的網(wǎng)的最小生成樹。
　　克魯斯卡爾（Kruskal）算法從另一途徑求網(wǎng)的最小生成樹。其基本思想是：假設(shè)連通網(wǎng)G=（V，E），令最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=（V，{}），概述圖中每個(gè)頂點(diǎn)自己成為一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)分別在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊而選擇下一條代價(jià)最小的邊。依此類推，直至T中所有頂點(diǎn)構(gòu)成一個(gè)連通分量為止。
　　本文內(nèi)容整理于網(wǎng)絡(luò)，僅供參考。
　　關(guān)于2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)高頻考點(diǎn)“最小代價(jià)生成樹”的內(nèi)容，小編就給大家簡(jiǎn)單介紹到這里了。如果還有其他考研考試相關(guān)內(nèi)容想要了解的，就請(qǐng)登錄高頓考研頻道看看吧。
　　小編為2024考研的小伙伴們準(zhǔn)備了豐富的學(xué)習(xí)資料，點(diǎn)擊下方藍(lán)色圖片即可領(lǐng)取哦~
考研備考資料