Эффективность времени в алгоритме Крускала с использованием матрицы смежности в качестве структуры данных

Это псевдокод, который я использовал для алгоритма Крускала. Структура данных, которую я здесь использовал, представляет собой матрицу смежности. Получил порядок роста как 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

algorithm time-complexity adjacency-matrix kruskals-algorithm
person Gihan    schedule 01.02.2012    source источник
comment
В чем конкретно ваш вопрос? Прямо сейчас ты чувствуешь, что хочешь, чтобы мы просто проверили твою домашнюю работу за тебя.   -  person templatetypedef    schedule 01.02.2012
comment
нет братан .. я вычислил значение это n2. Но из всех исследований, которые я провел, я не смог найти объяснения использования матрицы смежности в краскале и временной сложности. Мне нужно экспертное заключение по временной сложности краскала ..   -  person Gihan    schedule 01.02.2012
comment
Кстати, псудокод неверен .. это на самом деле алгоритм dijestra   -  person Gihan    schedule 02.02.2012

Ответы (1)


arrow_upward
3
arrow_downward

В зависимости от вашей фактической реализации и задействованных структур данных временная сложность этого алгоритма может быть плохой. Вот почему списки смежности являются более подходящей структурой для алгоритма Крускала: вам нужно как можно быстрее идентифицировать две вещи:

  1. Найдите следующую мин. граница веса,

  2. Проверьте, соединяет ли ребро два разных дерева (или две вершины принадлежат одному компоненту).

Для достижения сложности O (N log N) это означает, что вам необходимо:

  1. сначала отсортируйте края по весу. Это сделает шаг, на котором вы ищете следующее ребро минимального веса, операцией O (1), и

  2. используйте такую ​​структуру, как union-find, чтобы быстро определить, какие вершины и в каких компонентах находятся.

Для справки вы можете проверить эту статью CodeProject (реализация C #).

person Groo    schedule 01.02.2012
comment
Есть шанс, что вы могли бы взглянуть на вопрос и ответить здесь, в Meta, и, возможно, обязать: meta.stackexchange.com/questions/121054 / был бы очень признателен. - person Kev; 02.02.2012
comment
@Kev: Привет, Кев, спасибо за информацию, я добавил ее в качестве ответа. Уточняю: после того, как я ответил, ветка была перенесена в CodeReview, но ответы не скопированы? Я думал, что обычно все двигается. - person Groo; 02.02.2012