Time complexity of Prim's MST Algorithm

Question

Can someone explain to me why is Prim's Algorithm using adjacent matrix result in a time complexity of O(V2)?

Globose

see cs.stackexchange.com – Bolometer

Answer 1

(Sorry in advance for the sloppy looking ASCII math, I don't think we can use LaTEX to typeset answers)

The traditional way to implement Prim's algorithm with O(V^2) complexity is to have an array in addition to the adjacency matrix, lets call it distance which has the minimum distance of that vertex to the node.

This way, we only ever check distance to find the next target, and since we do this V times and there are V members of distance, our complexity is O(V^2).

This on it's own wouldn't be enough as the original values in distance would quickly become out of date. To update this array, all we do is at the end of each step, iterate through our adjacency matrix and update the distance appropriately. This doesn't affect our time complexity since it merely means that each step takes O(V+V) = O(2V) = O(V). Therefore our algorithm is O(V^2).

Without using distance we have to iterate through all E edges every single time, which at worst contains V^2 edges, meaning our time complexity would be O(V^3).

Proof:

To prove that without the distance array it is impossible to compute the MST in O(V^2) time, consider that then on each iteration with a tree of size n, there are V-n vertices to potentially be added.

To calculate which one to choose we must check each of these to find their minimum distance from the tree and then compare that to each other and find the minimum there.

In the worst case scenario, each of the nodes contains a connection to each node in the tree, resulting in n * (V-n) edges and a complexity of O(n(V-n)).

Since our total would be the sum of each of these steps as n goes from 1 to V, our final time complexity is:

(sum O(n(V-n)) as n = 1 to V) =  O(1/6(V-1) V (V+1)) = O(V^3)

QED

Bolometer

> The traditional way to implement Prim's algorithm with O(V^2) complexity is to have an array in addition to the adjacency matrix, lets call it distance which has the minimum distance of that vertex to the node. Could you elaborate on what the array is, and what you put in it? And: lets call it, what is 'it' - the array or adjacency matrix? – Bartender

Ignore my above comment, someone wrote a better explanation below – Bartender

Answer 2

Note: This answer just borrows jozefg's answer and tries to explain it more fully since I had to think a bit before I understood it.

Background

An Adjacency Matrix representation of a graph constructs a V x V matrix (where V is the number of vertices). The value of cell (a, b) is the weight of the edge linking vertices a and b, or zero if there is no edge.

Adjacency Matrix

   A B C D E
--------------
A  0 1 0 3 2
B  1 0 0 0 2
C  0 0 0 4 3
D  3 0 4 0 1
E  2 2 3 1 0

Prim's Algorithm is an algorithm that takes a graph and a starting node, and finds a minimum spanning tree on the graph - that is, it finds a subset of the edges so that the result is a tree that contains all the nodes and the combined edge weights are minimized. It may be summarized as follows:

1. Place the starting node in the tree.
2. Repeat until all nodes are in the tree:
   1. Find all edges that join nodes in the tree to nodes not in the tree.
   2. Of those edges, choose one with the minimum weight.
   3. Add that edge and the connected node to the tree.

Analysis

We can now start to analyse the algorithm like so:

1. At every iteration of the loop, we add one node to the tree. Since there are V nodes, it follows that there are O(V) iterations of this loop.
2. Within each iteration of the loop, we need to find and test edges in the tree. If there are E edges, the naive searching implementation uses O(E) to find the edge with minimum weight.
3. So in combination, we should expect the complexity to be O(VE), which may be O(V^3) in the worst case.

However, jozefg gave a good answer to show how to achieve O(V^2) complexity.

Distance to Tree

            | A  B  C  D  E
            |----------------
Iteration 0 | 0  1* #  3  2
          1 | 0  0  #  3  2*
          2 | 0  0  4  1* 0
          3 | 0  0  3* 0  0
          4 | 0  0  0  0  0

NB. # = infinity (not connected to tree)
    * = minimum weight edge in this iteration

Here the distance vector represents the smallest weighted edge joining each node to the tree, and is used as follows:

1. Initialize with the edge weights to the starting node A with complexity O(V).
2. To find the next node to add, simply find the minimum element of distance (and remove it from the list). This is O(V).
3. After adding a new node, there are O(V) new edges connecting the tree to the remaining nodes; for each of these determine if the new edge has less weight than the existing distance. If so, update the distance vector. Again, O(V).

Using these three steps reduces the searching time from O(E) to O(V), and adds an extra O(V) step to update the distance vector at each iteration. Since each iteration is now O(V), the overall complexity is O(V^2).

Adjourn

This answer is brilliant! This should be the correct answer! – Bartender

Answer 3

First of all, it's obviously at least O(V^2), because that is how big the adjacency matrix is.

Looking at http://en.wikipedia.org/wiki/Prim%27s_algorithm, you need to execute the step "Repeat until Vnew = V" V times.

Inside that step, you need to work out the shortest link between any vertex in V and any vertex outside V. Maintain an array of size V, holding for each vertex either infinity (if the vertex is in V) or the length of the shortest link between any vertex in V and that vertex, and its length (so in the beginning this just comes from the length of links between the starting vertex and every other vertex). To find the next vertex to add to V, just search this array, at cost V. Once you have a new vertex, look at all the links from that vertex to every other vertex and see if any of them give shorter links from V to that vertex. If they do, update the array. This also cost V.

So you have V steps (V vertexes to add) each taking cost V, which gives you O(V^2)

Luckily