New answers tagged


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.


Notice that removing any edge $e\in T\setminus T'$, from $T$ itself, will result in two connected components: $V,U$. Since $T'$ is a tree, it is connected. Therefore, there must be some edge $e'\in T'$ between the components $V$ and $U$. I claim, the three following things: $e'\notin T$ By removing $e$ from $T$ and adding instead $e'$, we get a tree $\hat T$...


Add an edge to a spanning tree and you have a cycle. Deleting any edge in that cycle results in a new spanning tree.


Consider the following example: You can clearly see that the heaviest edge (connecting vertices 3 and 4) is in any MST of this graph. In general, the heaviest edge (assuming it is unique) will be part of the MST of a graph if and only if it is a bridge (meaning that if we remove that edge the graph gets disconnected). The condition $|E| \geq |V| - 1$ doesn'...


Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave. There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still ...

Top 50 recent answers are included