Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $$x$$ and $$y$$ is it possible to make a faster algorithm than Prim's algorithm or Kruskal's algorithm?

I saw on Kruskal's algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don't think there is any benefit, but I am not sure...

1 Answer

No, Kruskal's algorithm doesn't make any assumptions about how fast edges can be sorted. I suspect you misinterpreted what you read. Kruskal's algorithm doesn't make assumptions.

You linked to a Wikipedia article. It states:

Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in O(E α(V)) time

"Provided" means "If", not "We assume that".

If you use a standard sorting algorithm that takes $$O(E \log E)$$ time, then Kruskal's algorithm runs in $$O(E \log E)$$ time. If you are in a special situation where there is a way to sort the edges in linear time (e.g., using counting sort), then Kruskal's algorithm can be implemented in a way that takes $$O(E \alpha(V))$$ time, which is faster. But there is no assumption that you will always be in that special situation; usually, you won't.

The case where there are only two edge weights is indeed such a special situation, and thus Kruskal's algorithm can be implemented in a way that is asymptotically faster for such graphs than for general graphs.