Оптимизация MST с использованием алгоритма Prim от O (n^3) до O (n^2)

Question

Ниже приведен мой псевдокод для преобразования подключенного графика в MST с использованием алгоритма Prim. Однако я получаю сложность n^3, а не n^2. Пожалуйста, помогите мне разобраться в необязательных шагах. У меня есть матрица смежности «a», чтобы сохранить вес графов графа и двумерную матрицу «проверить», сохраняя «1» для вершин, уже находящихся в дереве, и «0» для остальных.

Также обратите внимание, что это также можно сделать в nlog (n), но я не хочу ссылаться на какой-либо существующий псевдокод и хочу попробовать его самостоятельно. Я был бы признателен за ответ, оптимизирующий мой собственный подход.

Initialize check. //check[0][1]==1 
while(--no_of_vertices) 
{ 
    minimum_outer = infinite 
    for(i from 1 to no_of_vertices) 
     { 
      minimum_inner = infinite 
      select i from check having value 1 
      for(j from 1 to no_of_vertices) 
      { 

       select j from check having value 0 
       if(a[i-j] < minimum_inner) 
        minimum_inner = a[i-j] 
        temp_j = j; 
      } 
      if(minimum_inner<minimum_outer) 
      { 
       minimum_outer = minimum_inner 
       final_i = i 
       final_j = temp_j 
      } 

     } 

     //until here basically what I have done is, selected an i-j with lowest 
     //weight where "i" is chosen from vertices already in MST and "j" from 
     //remaining vertices 

     check[final_j][1] = 1 
     print final_i - final_j 
     cost_of_mst += a[final_i][final_j] 
} 

Answer 1

Причина ваш алгоритм работает с O(V^3) времени, потому что в каждой итерации вы собираетесь через всю матрицу смежности, которая принимает O(V^2) и выполняет некоторые избыточные действия.

Всякий раз, когда вы добавляете вершину к охватывающему дереву, не более |V-1| новых ребер, которые могут быть добавлены к решению. На каждой итерации вам нужно только проверить, изменили ли эти края минимальный вес каждой из других вершин.

Алгоритм должен выглядеть следующим образом:

1. Select a random vertex v, add v to S, assign an array A where A[i] = d{v, i} 
2. While there are vertices that belong to G and not to S do: 
    2.1. Iterate through A, select the minimum value A[i], add vertex i to S 
    2.2. for each edge e={i, j} connected to vertex i do: 
     2.2.1. if d{i, j} < A[j] then A[j] = d{i ,j} 

Таким образом, вы выполняете O(V) действия для каждой вершины вы добавляете вместо O(V^2), и общее время работы составляет O(V^2)

Вот редактировать ваш код :

Select a random vertex x 
Initialize DistanceTo    // DistanceTo[i] = d{x, i} 
Initialize Visited     // Visited[i] = false if i!=x, Visited[x] = true 

while(--no_of_vertices) 
{ 
    min_val = infinite 
    min_index = 1; 
    for(i from 1 to DistanceTo.size) 
    { 
     if (Visited[i] = false && DistanceTo[i] < min_val) 
     { 
      min_val = DistanceTo[i] 
      min_index = i 
     } 
    } 

    Visited[min_index] = true 

    For(i from 1 to Distance.size) 
    { 
     if (Visited[i] = false && d{min_index, i} < DistanceTo[i]) 
     { 
      DistanceTo[i] = d{min_index, i} 
     } 
    } 

    print edge {min_index, i} was added to the MST 
    cost_of_mst += d{min_index, i} 
}