關于克魯斯卡爾算法的時間復雜度是多少，什么是克魯斯卡爾算法這個問題很多朋友還不知道，今天小六來為大家解答以上的問題，現在讓我們一起來看看吧！
1、計算最小生成樹的算法克魯斯卡爾算法 假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。
2、之后，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。
3、依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。
本文分享完畢，希望對大家有所幫助。
標簽：
免責聲明：本文由用戶上傳，與本網站立場無關。財經信息僅供讀者參考，并不構成投資建議。投資者據此操作，風險自擔。 如有侵權請聯系刪除！