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