Find minimal spanning tree of graph with edge values from 1 to 5 integers How can I find the minimal spanning tree of graph with edge values from 1 to 5 integers (no need to be unique) most effectively? I know I can use Kruskal algorithm, but how can I modify the algorithm to find it faster when I know there are edges with values only 1, 2, 3, 4 or 5? I cant figure it out how it could be faster when I know this limitation on edges.
Take a look at the complexity of Kruskal's algorithm. Since the edges are with integer weights, you can sort them in linear time. The entire algorithm will take a total of $O(|V|\alpha(|E|)+|E|)$. We need $O(|E|)$ to sort, and an additional $O(|V|\alpha(|E|))$ for Kruskal's algorithm.