0

これは、クラスカルのアルゴリズムに使用した擬似コードです。ここで使用したデータ構造は隣接行列です。私は成長の順序を取得しました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
4

1 に答える 1

3

実際の実装と関連するデータ構造によっては、このアルゴリズムの時間計算量が悪くなる可能性があります。そのため、隣接リストはクラスカルのアルゴリズムにとってより適切な構造です。2つのことをできるだけ早く識別できる必要があります。

  1. 次の分を見つけます。ウェイトエッジ、

  2. エッジが2つの異なるツリーを接続しているかどうか（または2つの頂点が同じコンポーネントに属しているかどうか）を確認します。

O（N log N）の複雑さを実現するには、次のことを行う必要があります。

  1. 最初に重みでエッジを並べ替えます。これにより、次の最小ウェイトエッジを探しているステップがO（1）操作になります。

  2. union-findのような構造を使用して、どの頂点がどのコンポーネントにあるかをすばやく識別します。

参考までに、このCodeProjectの記事（C＃実装）を確認できます。

于 2012-02-01T12:35:37.243 に答える