對計算機考研感興趣的同學趕緊看過來,這里是小編整理的有關2024計算機考研數(shù)據(jù)結(jié)構(gòu)考點“最小代價生成樹”的內(nèi)容,快來看看吧!希望能對大家有所參考。
2024計算機考研數(shù)據(jù)結(jié)構(gòu)高頻考點“最小代價生成樹”
  無向連通圖的生成樹是一個極小連通子圖,它包括圖中全部頂點,并且有盡可能少的邊。
  無向連通網(wǎng)絡的最小代價生成樹是所有生成樹中邊的權(quán)值之和最小的。
  (1)普里姆算法:
  首先,從n個頂點中任選一個頂點v加入到原來為空的生成樹中;然后,重復執(zhí)行下列操作:從一個頂點在生成樹中,而另一個頂點不在生成樹中的那些邊中,選取一條權(quán)值最小的邊,并將這條邊以及它所關聯(lián)的目前還不在生成樹中的那個頂點加入到生成樹中。當生成樹中的頂點數(shù)達到n時,整個構(gòu)造過程結(jié)束。
  (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中所有頂點構(gòu)成一個連通分量為止。
  本文內(nèi)容整理于網(wǎng)絡,僅供參考。
  關于2024計算機考研數(shù)據(jù)結(jié)構(gòu)高頻考點“最小代價生成樹”的內(nèi)容,小編就給大家簡單介紹到這里了。如果還有其他考研考試相關內(nèi)容想要了解的,就請登錄高頓考研頻道看看吧。
  小編為2024考研的小伙伴們準備了豐富的學習資料,點擊下方藍色圖片即可領取哦~
考研備考資料