Optimising MST using Prim's algorithm from O(n^3) to O(n^2)

Question

Following is my pseudocode for converting a connected graph to MST using Prim's algorithm. I am however getting a complexity of n^3 rather then n^2. Please help me figure out the non-required steps.I have an adjacency matrix "a" to store the weight of graph edges and a 2D matrix "check" storing "1" for vertices already in the tree and "0" for remaining.

Please also note that this can be done in nlog(n) also, but I don't want to refer any existing pseudocode and want to try it on my own. I would appreciate an answer optimizing my own approach.

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]
}

Ron Teller · Accepted Answer · 2013-10-14 09:35:11Z

1

The reason your algorithm runs with O(V^3) time is because in each iteration you are going through the entire adjacency matrix, which takes O(V^2) and performs some redundant actions.

Whenever you are adding a vertex to the spanning tree, there are at most |V-1| new edges that may be added to the solution. At each iteration, you should only check if these edges changed the minimal weight to each of the other vertices.

The algorithm should look like:

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}

This way you are performing O(V) actions for each vertex you add instead of O(V^2), and the overall running time is O(V^2)

Here's an edit to your code:

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}
}

edited Oct 14, 2013 at 9:35

answered Oct 13, 2013 at 7:12

Ron Teller

1,8901 gold badge12 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

java_doctor_101 Over a year ago

Thanks for replying.But as I asked in the question, is there any way to modify my own pseudocode rather then using another one, like the one you suggested. I wanted to know what changes can I do in my solution above.

Ron Teller Over a year ago

I've added a revision to your code, as you can see there were major changes as the logic it implements is different, I don't think you can do a smaller revision if you want the code to run with O(n^2) time

Collectives™ on Stack Overflow

Optimising MST using Prim's algorithm from O(n^3) to O(n^2)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related