データ構造として隣接行列を使用する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

実際の実装と関連するデータ構造によっては、このアルゴリズムの時間が複雑になることがあります。あなたはできるだけ速く二つのことを識別できるようにする必要があります：

1. は、次の分を探す隣接リストはクラスカル法のためのより適切な構造です理由です。

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

   1. ソートエッジ最初の重量：Oを実現するために

   （N Nをログ）複雑さ、これはあなたがする必要があるということです。つまり、次の最小量を探しているステップは、（1）運転Oエッジになります、そして

3. は組合-見つけるがどのコンポーネントに記載されていた頂点迅速に特定するような構造を使用します。

参考のために、あなたはthis CodeProject article（C＃実装）を確認することができます。