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.
1
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/140344/755, stackoverflow.com/q/67432796/781723. Please do not post the same question on multiple sites. $\endgroup$– D.W. ♦May 16, 2021 at 6:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered May 15, 2021 at 12:08
-
$\begingroup$ so what is the modification? how can I fasten it when I know the values are 1-5 in comparison to e.g. graph with values 1-5000? $\endgroup$ May 15, 2021 at 12:13
-
$\begingroup$ Read the last paragraph in the link. It explains what needs to be done and what the complexity will be $\endgroup$ May 15, 2021 at 12:50