# 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...

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.