Temporal complexity of the Prim MST algorithm

Question

Can someone explain to me why the Prim algorithm using the adjacent matrix leads to the time complexity of O(V 2 ) ?

Answer 1

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

The traditional way to implement the Prim algorithm with complexity O(V^2) is to have an array in addition to the adjacency matrix, you can call it distance , which has a minimum distance to this vertex from node.

Thus, we always check distance to find the next target, and since we do it V times and there are V distance members, our complexity is O(V^2) .

This would not be enough, since the initial values ​​in distance quickly outdated. To update this array, everything we do is at the end of each step, iterate through our adjacency matrix and update the distance accordingly. This does not affect our time complexity, as it simply 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 over all the edges of E every time, which in the worst case contains V ^ 2 edges, which means that our time complexity will be O(V^3) .

Evidence:

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

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

In the worst case, each node contains a connection to each node in the tree, resulting in edges n * (Vn) and complexity O(n(Vn)) .

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

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

QED

Answer 2

Note. This answer simply takes jozefg's answer and tries to explain it more fully, as I had to think a bit before I understood it.

Background

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

 Adjacency Matrix ABCDE -------------- 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 Algorithm is an algorithm that takes a graph and a start node, and finds the minimum spanning tree on the graph - that is, it finds a subset of the edges so that the result is a tree containing all the nodes, and the combined edge weights are minimized. It can be summarized as follows:

• Put the starting node in the tree.
• Repeat until all nodes are in the tree:
  • Find all edges connecting nodes in the tree with nodes not contained in the tree.
  • From these ribs, select the one with the minimum weight.
  • Add this tree and the connected node to the tree.

Analysis

Now we can begin to analyze the algorithm as follows:

• At each iteration of the loop, add a node to the tree. Since there are V nodes, it follows that there are O (V) iterations of this cycle.
• In each iteration of the loop, we need to find and check the edges in the tree. If there are edges E, the naive search implementation uses O (E) to find the edge with minimal weight.
• So, combined, we should expect that the complexity will 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 | ABCDE |---------------- 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 is the smallest weighted edge connecting each node to the tree, and is used as follows:

• Initialize with weights to source node A with O (V) complexity.
• To find the next node to add, simply find the minimum distance element (and remove it from the list). This is O (V).
• After adding a new node, there are O (V) new edges connecting the tree with the other nodes; for each of them, it is determined whether 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 search time from O (E) to O (V) and adds an additional step O (V) to update the distance vector at each iteration. Since each iteration is now equal to O (V), the overall complexity is O (V ^ 2).

Answer 3

First of all, this is obvious, at least O (V ^ 2), because this is the maximum adjacency matrix.

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

Inside this step, you need to develop the shortest connection 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 connection between any vertex in V and this vertex and its length (so in the beginning it comes only from the length of the connections between the initial vertex and every other vertex). To find the next vertex to add to V, just search this array for price V. After you have a new vertex, look at all the links from this vertex to each other vertex and see if any of them give short links from V to this top. If they do, update the array. It also costs V.

So, you have V steps (V-vertices to add), each of which takes the cost of V, which gives you O (V ^ 2)