1

以下是我使用 Prim 算法将连通图转换为 MST 的伪代码。然而，我得到的复杂度是 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]
}
4

1 回答 1

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}
}
于 2013-10-13T07:12:21.940 回答