问题描述
这是我用于Kruskal算法的伪代码.我在这里使用的数据结构是一个邻接矩阵.我得到的成长顺序为 n ^ 2 .我想知道它是否正确.
This is the pseudo code I used for Kruskal's algorithm. The data structure I have used here is an adjacency matrix. I got the order of growth as n^2. I want to know whether it is correct or not.
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
推荐答案
取决于您的实际实现和所涉及的数据结构，此算法的时间复杂度可能很差.这就是为什么邻接列表是Kruskal算法更合适的结构的原因:您需要能够尽快识别出两件事:
Depending on your actual implementation and data structures involved, time complexity of this algorithm can be bad. That is why adjacency lists are a more appropriate structure for Kruskal's algorithm: you need to be able to identify two things as fast as possible:
-
查找下一个分钟.重量边缘，
Find the next min. weight edge,
检查边缘是否连接了两棵不同的树(或两个顶点属于同一组件).
Check if an edge connects two different trees (or if two vertices belong to the same component).
要实现O(N log N)复杂度，这意味着您需要:
To achieve O(N log N) complexity, this means you need to:
- 首先按重量
-
对边缘进行排序.这将使您正在寻找下一个最小权重边的步骤成为O(1)操作，并且
sort the edges by weight first. That will make the step where you are looking for the next minimum weight edge an O(1) operation, and
使用类似 union-find 的结构来快速确定哪些顶点位于哪些组件中.
use a structure like union-find to identify quickly which vertices are in which components.
作为参考，您可以查看此CodeProject文章(C#实现)
For reference, you can check this CodeProject article (a C# implementation).
这篇关于使用邻接矩阵作为数据结构的Kruskal算法中的时间效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！