kruskal演算法時間復雜度

Ⅰ kruskal演算法是什麼

kruskal演算法是：克魯斯卡爾演算法。禪緩是求連通網的最小生成樹的另一種方法。與普里姆演算法不同，它的時間復雜度為O（eloge）、（e為網中的邊數）租襲野，所以，適合於求邊稀疏的網的最小生成樹。

克魯斯卡爾（Kruskal）演算法從另一途徑求網的最小生成樹。其基本思想是：假設連通網G=（V，E），令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{}），概述圖中每個頂點自成一個連通分量。

在E中選擇代價最小的邊，若該邊依附的頂點分別在T中不同的連通分量上，則將此邊加入到T中；否則，捨去此邊而選擇下一條代價最小的邊。依此類推，直至T中所有頂點構成一個連通分量為止。

復雜度：

克魯斯卡爾演算法的時間復雜度主要由排序方法決定，而克魯斯卡爾演算法的排序方法只與網中邊的條數有關，而與網中頂點的個數無關，當使用時間復雜度為O（elog2e）的排序方法時，克魯斯卡爾演算法的時間復雜度即為O（log2e），因此當網的頂點個數較多、而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成弊喊樹效果較好。

Ⅱ 克魯斯卡爾演算法的時間復雜度為多少

時間復雜度為O(|E|log|E|)，其中E和V分別是圖的邊集和點集。

基本思想是先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹。

反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

(2)kruskal演算法時間復雜度擴展閱讀：

克魯斯卡爾演算法證明

假設G=(V,E) 是一個具有n個頂點的連通網，T=(U,TE)是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空集。該演算法的基本思想是：將圖G中的邊按權值從小到大的順序依次選取。

若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去直到TE中包含n-1條邊為止，此時的T即為最小生成樹。

克魯斯卡爾演算法，至多對e條邊各掃描一次，每次選擇最小代價的邊僅需要O(loge)的時間。因此，克魯斯卡爾演算法的時間復雜度為O(eloge)。

Ⅲ 數據結構（十）：最小生成樹

最小生成樹是帶權無向連通圖中權值最小的生成樹，根據 圖 中生成樹定義可知， 個頂點的連通圖中，生成樹中邊的個數為 ，向生成樹中添加任意一條邊，則會形成環。生成樹存在多種，其中權值之和最小的生成樹即為最小生成樹。

若 為最小生成樹 的一個真子集，即 的頂點集合和邊集合都是 的頂點和邊集合的子集，構造最小生成樹過程為向 中添加頂點和邊，添加的原則有兩種：

kruskal 演算法即為上述第一種原則，通過選擇圖中的最小權值邊來構造最小生成樹，過程中需要注意避免形成環。

step 1：
最小權值邊為頂點 7、8 形成的邊

step 2：
最小權值邊為頂點 3、9 形成的邊

step 3：
最小權值邊為頂點 6、7 形成的邊

step 4：
最小權值邊為頂點 3、6 形成的邊

step 5：
最小權值邊為頂點 1、2 形成的邊

step 6：
最小權值邊為頂點 3、4 形成的邊

step 7：
最小權值邊為頂點 1、8 形成的邊

step 8：
最小權值邊為頂點 4、5 形成的邊

最小生成樹的權值之和為 37

這里使用鄰接表作為圖的存儲結構

這里使用 getEdgesFromAdjacencyList 函數完成鄰接表到邊集合的轉換，使用快排 sort 完成對邊集合的排序，使用 origin 函數返回每個子圖的根。

該函數返回頂點 index 所屬子圖的根頂點，其中 vertices[index] 位置上存儲的是頂點 index 的上一個頂點，每個子圖中，根頂點的上一個頂點為自身。

kruskal 演算法中使用 getEdgesFromAdjacencyList 函數完成鄰接表向邊集合的轉換，函數內部存在兩層循環，訪問鄰接表中每個頂點的相鄰頂點，復雜度為 。使用快排對邊集合進行排序，時間復雜度為 ，因為 ，所以快排時間復雜度可以表述為 。 kruskal 演算法中 while 循環取最小權值邊，並對邊的兩個頂點執行 origin 函數判斷是否屬於同一個子圖，時間復雜度為 。所以 kruskal 演算法的時間復雜度為 。

kruskal 演算法的過程為不斷對子圖進行合並，直到形成最終的最小生成樹。 prim 演算法的過程則是只存在一個子圖，不斷選擇頂點加入到該子圖中，即通過對子圖進行擴張，直到形成最終的最小生成樹。

step 1：
距離子圖的最近頂點為 4

step 2：
距離子圖的最近頂點為 3

step 3：
距離子圖的最近頂點為 9

step 4：
距離子圖的最近頂點為 6

step 5：
距離子圖的最近頂點為 7

step 6：
距離子圖的最近頂點為 8

step 7：
距離子圖的最近頂點為 2

step 8：
距離子圖的最近頂點為 1

最小生成樹的權值之和為 37

這里使用鄰接表作為圖的存儲結構

這里使用 vertices 列表存儲每個頂點元素，每個元素包括兩個屬性， index 為頂點下標， weight 為頂點距離子圖的大小。演算法中使用 verticesIndex 列表存儲每個頂點元素在 vertices 列表中的下標位置。使用 heapSort 堆排序對每個頂點到子圖的距離進行排序，即對 vertices 列表進行排序，使用堆排序內的 transformToHeap 函數調整 vertices 列表為小頂堆。當添加新頂點到子圖後，使用 updateVertices 函數完成對相鄰頂點的距離更新。

當 vertices 列表調整為小頂堆之後，將列表首、尾元素交換，則列表尾元素即為距離子圖最近的頂點元素。

對每一個相鄰頂點，如果不在子圖中，則判斷是否更新到子圖的距離。更新距離後的 while 循環操作，目的為調整堆結構為小頂堆。

prim 演算法中構造頂點列表的時間復雜度為 。使用堆排序對頂點列表進行排序，時間復雜度為 。 prim 演算法中 while 循環取最近頂點元素，並調整元素取出後列表的堆結構，所以調整復雜度為 ；同時，循環結構內執行 updateVertices 函數，更新每個取出頂點的相鄰頂點距離值，所以更新頂點數為 ，因為每個頂點更新距離後，需要調整堆結構為小頂堆，所以更新復雜度為 。所以 prim 演算法的總時間復雜度為 。

Ⅳ 最小生成樹兩種演算法有何區別

主要有兩個：
1.普里姆（prim)演算法
特點：時間復雜度為御老o(n2).適合於求邊稠密鎮森升的最小生成樹。
2.克魯斯卡爾（kruskal)演算法
特點：時間復雜度為o(eloge)(e為網中邊數），適合於春蔽求稀疏的網的最小生成樹。