使用Prim算法从O（n^3）到O（n^2）优化MST

Question

以下是我使用Prim算法将连通图转换为MST的伪代码。然而，我得到了n^3的复杂度，而不是n^2。请帮我弄清楚不需要的步骤。我有一个邻接矩阵“a”来存储图边的权重，一个2D矩阵“检查”存储树中已经存在的顶点“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} 
}