使用邻接矩阵作为数据结构的Kruskal算法中的时间效率 [英] Time efficiency in Kruskal's algorithm using adjacency matrix as data structure

问题描述

这是我用于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:

1. 查找下一个分钟.重量边缘，

1. 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:

首先按重量

1. 对边缘进行排序.这将使您正在寻找下一个最小权重边的步骤成为O(1)操作，并且

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算法中的时间效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！