Algorithm to Compute Minimum Spanning Tree

The minimum spanning tree (MST) of a graph is a tree that connects all the vertices of the graph with the minimum possible total edge weight. The algorithm to compute the MST of a graph can be implemented using different approaches, such as Kruskal's algorithm and Prim's algorithm.

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that selects the minimum-weight edge in each iteration and adds it to the MST if it does not create a cycle. The algorithm maintains a forest of trees, where each vertex is initially in its own tree. The algorithm repeatedly selects the minimum-weight edge that connects two trees and merges the trees into one. The algorithm stops when there is only one tree left, which is the MST.

The time complexity of Kruskal's algorithm is O(m log m), where m is the number of edges in the graph. This is because the algorithm sorts the edges in non-decreasing order of weight, which takes O(m log m) time using a sorting algorithm such as quicksort.

Prim's Algorithm

Prim's algorithm is also a greedy algorithm that builds the MST one vertex at a time. The algorithm starts with an arbitrary vertex and adds the minimum-weight edge that connects the tree to a vertex that is not yet in the tree. The algorithm maintains a set of vertices that are in the tree and a set of vertices that are not yet in the tree. In each iteration, the algorithm adds the minimum-weight edge that connects a vertex in the tree to a vertex outside the tree and adds the vertex to the tree. The algorithm stops when all vertices are in the tree, which is the MST.

The time complexity of Prim's algorithm is O(m log n), where n is the number of vertices in the graph. This is because the algorithm uses a priority queue to select the minimum-weight edge in each iteration, which takes O(log n) time for each edge. The total time for all edges is O(m log n).

Answer to the Question

The given graph has m edges with the same weight, so Kruskal's algorithm can be modified to have a time complexity of O(m n). In this modified algorithm, the edges are not sorted, and the minimum-weight edge is found by iterating over all edges. Since all edges have the same weight, iterating over all edges takes O(m) time. The algorithm maintains a forest of trees and repeatedly selects the minimum-weight edge that connects two trees and merges the trees into one. The algorithm stops when there is only one tree left, which is the MST.

Therefore, the correct answer is option 'A', O(m n).