Minimum Spanning Tree - Algorithm

[L4N0]

Homework Statement

Suppose a weighted connected graph G = (V,E) has n edges.
Describe an algorithm to find a Minimum Spanning Tree of G in O(n) time. Prove the correctness of your answer. (Here n = |V |).

Homework Equations

I know about DFS, BFS, Prims algorithm

The Attempt at a Solution

I was thinking of running something similar to Breadth first search (BFS).
Keep track of edges part of MST (call it EMST), and vertices part of MST (call it VMST)
--
-select a vertex
-look at all adjacent edges and find the one with minimum weight (by keeping a variable 'min' and updating it as we loop)
-put the min edge in EMST, so we don't look at it again
-put the current vertex and the other vertex connected by the edge both in VMST
-then for all vertices in VMST repeat the procedure (so look at all of their vertices and find min to add to the VMST)
--

I'm not sure if this procedure is O(n), I'm afraid it might be slower, but I can't think of a way to improve it. I'm also a bit unsure how to take advantage of n=|V|

 

[KataKoniK]

.

To prove the correctness, we can use the fact that a Minimum Spanning Tree is a connected subgraph of a given graph G that connects all vertices together with the minimum possible total edge weight. So, by adding the minimum weighted edge at each step, we are ensuring that the total weight of the Minimum Spanning Tree is minimized. Also, since we are only considering edges that have not been added to the Minimum Spanning Tree yet, we are avoiding cycles and ensuring that the final result is a tree. Therefore, the algorithm will always produce a Minimum Spanning Tree of G.

To improve the efficiency of this algorithm, we can use a data structure such as a priority queue to store the edges and their weights, which would allow us to find the minimum weighted edge in constant time. This would make the overall time complexity of the algorithm O(n log n), which is faster than O(n). Additionally, we can use the fact that G is a connected graph to reduce the number of iterations needed, as we only need to iterate through each vertex once instead of iterating through all the vertices in VMST. This would further improve the efficiency of the algorithm.

 

[Mene]

.

Your algorithm is a variation of Prim's algorithm, which is a well-known algorithm for finding the minimum spanning tree in a weighted graph. However, your algorithm has a time complexity of O(n^2) since you are looping through all vertices for each vertex in VMST, resulting in a total of n^2 iterations. To achieve a time complexity of O(n), you can use a different approach called Kruskal's algorithm.

Kruskal's algorithm works by sorting all the edges in increasing order of their weight and then adding them one by one to the MST if they do not create a cycle. This can be done in O(nlogn) time using efficient sorting algorithms like quicksort or mergesort. After sorting the edges, you can use the union-find data structure to check for cycles while adding edges to the MST. The union-find data structure helps in keeping track of which vertices are already connected in the MST, thus preventing the creation of cycles.

To prove the correctness of Kruskal's algorithm, we can use the cut property, which states that the minimum weight edge crossing any cut in a graph must be a part of the MST. In Kruskal's algorithm, we are essentially finding the minimum weight edge that does not create a cycle, which is the same as finding the minimum weight edge crossing a cut. Therefore, by adding these edges one by one, we are creating the MST with the minimum weight.

In conclusion, Kruskal's algorithm is an efficient way to find the minimum spanning tree in a weighted graph in O(nlogn) time. It is based on the cut property and uses the union-find data structure to prevent the creation of cycles. By sorting the edges in increasing order of their weight, we can ensure that we are always adding the minimum weight edge that does not create a cycle.