0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.