Linear Time Algorithm for MST

Question

I was wondering if anyone could point to a linear time algorithm to find the MST of a graph when there are a small number of weights (I. edges can have only 2 different weights).

I could not find anything on Google except Prim's, Kruskal's, Boruvka, none of which seem to have properties that would shorten the runtime in this special case. I assume that for its linear time it should be some kind of BFS modification (which finds MST when the weights are uniform).

Answer 1

The reason for the factor lg V in the Prim O(V lg V) working environment O(V lg V) is the heap that is used to search for the next candidate edge. I am sure that you can create a priority queue that does insertion and deletion at a constant time when there is a limited number of possible weights, which will reduce Prim to O(V) .

For the priority queue, I believe that this is enough for an array whose indices cover all possible weights, where each element points to a linked list containing elements with this weight. You still have a coefficient d (the number of different weights) to determine which list to output the next element from (the "lowest" is nonempty), but if d is a constant, then everything will be fine.

Answer 2

Developing the answer of Aasmund Eldhuset: if the weights in MST are limited by numbers in the range 0, 1, 2, 3, ..., U-1, then you can adapt many of the existing algorithms to run in (near) linear time, if U is a constant .

For example, take the Kruskal algorithm. The first step in the Kruskal algorithm is sorting the edges in order of increasing weight. You can do this in time O (m + U) if you use count sorting or time O (m lg U) if you use radix sort. If U is a constant, then both of these sorting procedures take linear time. Therefore, the execution time of the Kruskal algorithm in this case will be O (m? (M)), where? (m) is the inverse function of Ackerman, since the limiting factor will be the time it takes to save the disjoint states to establish the forest.

As an alternative, consider the Prim algorithm. You need to maintain a priority queue of distances between candidates to nodes. If you know that all edges are in the range [0, U), then you can do it in a naively naive way by simply saving the array from the U bucket, one at a time to one of the possible priorities. When inserting into the priority queue, it just requires that you drop the item into the right bucket. You can make a decrease button by displacing an item and moving it to the bottom bucket. Then you can search for mines by scanning the buckets. This causes the execution time of the algorithm to be O (m + nU), which is linear if U is a constant.