使用鄰接矩陣作爲數據結構的Kruskal算法的時間效率

Question

這是我用於Kruskal算法的僞代碼。我在這裏使用的數據結構是一個鄰接矩陣。我得到的增長順序爲n^2。我想知道這是否正確。

Kruskal’s Pseudo code 

1. Kruskal (n, m, E) 
2. // Purpose to compute the minimum spanning tree using Kruskal's algorithm 
3. // Inputs 
4. n - Number of vertices in the graph 
5. m - Number of edges in the graph 
6. E - Edge list consisting of set of edges along with equivalent weight 
    w - cost adjacency matrix with values >0 
7. con – constrain adjacency matrix 
8. // Output: - the minimum spanning tree along 
9. count - shortest distance from the source to all other nodes 
d - shortest distance from source to all other nodes 
10. p - shortest path from source to destination 
11. s - gives the nodes that are so far visited and nodes that are not visited 
12. s [source] <- 1 
13. For i = 0 to n-1 Do 
14. If con[u, i] == T Then 
15.  add u to S 
16.  select edge that need to be connected 
17.  add cost associated with edge to get total cost of minimal spanning tree 
18. Else 
19.  find u and d[u] such that d[u] is minimum and u Є V - S 
20.  add u to S 
21. End If 
22. If u = destination Then 
23.  End 
24. End If 
25. For every v Є V - S Do 
26.  If con[u, v] == T Then 
27.   d[v] <- d[u] + w[u, v] 
28.   p[v] <- u 
29.  ElseIf d[u] + w[u, v]<d[v] Then 
30.   d[v] <- d[u] + w[u, v] 
31.   p[v] <- u 
32.  End If 
33. End For 
34. End For 

Answer 1

根據您的實際實施和涉及的數據結構，此算法的時間複雜性可能會很差。這就是爲什麼鄰接表是Kruskal算法更合適的結構：你需要能夠以最快的速度找出兩件事情儘可能：

1. 查找下一個分鐘。重量邊緣，

2. 檢查邊緣是否連接兩棵不同的樹（或者如果兩個頂點屬於同一個組件）。

要達到O（N日誌N）的複雜性，這意味着您需要：

1. 排序邊緣重量第一。這將使您正在尋找O（1）操作的下一個最小權重邊的步驟，並且使用諸如聯合發現的結構快速識別哪些頂點位於哪些組件中。

僅供參考，您可以檢查this CodeProject article（C＃實現）。