这是我用于 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
最佳答案
根据您的实际实现和涉及的数据结构,此算法的时间复杂度可能很差。这就是为什么邻接列表更适合 Kruskal 算法的结构:您需要能够尽快识别两件事:
查找下一分钟。权重边,
检查边是否连接两个不同的树(或者两个顶点是否属于同一组件)。
要实现 O(N log N) 复杂度,这意味着您需要:
首先按权重对边进行排序。这将使您寻找下一个最小权重边缘的步骤成为 O(1) 操作,并且
使用类似union-find 的结构来快速识别哪些顶点位于哪些组件中。
作为引用,您可以查看this CodeProject article (C# 实现)。
关于algorithm - 使用邻接矩阵作为数据结构的 Kruskal 算法的时间效率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9092339/