I am now learning about MST and algorithms for finding it, like Prim's, Kruskal's and etc. However, what if we have a connected, undirected simple graph and all edges have a weight, BUT the possible weights are {1,10,100,1000}. Is it possible to find MST in O(m+n) time? I know that the data structure matters when we are talking about the time complexity, and we can use something like Fibonacci heaps to make it faster, but still, I have no idea how to make an algorithm with the running time O(n+m).
$\endgroup$1 Answer
$\begingroup$Using Prim's algorithm, you can achieve an $\mathcal{O}(n+m)$ complexity by using a bucket priority queue. This priority queue has all operations complexity constant or bounded by the number of possible weights, so constant in this case.
$\endgroup$
