Algorithm to cut the graph into a tree.

Question

Given a finite connected graph $G$, I can make a finite number of cuts on the edges to obtain a tree. What is the most efficient algorithm to perform this procedure?

Thanks, Vladimir

Answer 1

Your two best choices are either prim's algorithm or kruskal's algorithm. Prim's will start with a vertex $v$ and find the cheapest edge branching out from $v$, and add it to your set of edges. Now add the cheapest edge which touches exactly one of your vertices. Repeat this process until you have a spanning tree. Kruskal's algorithm requires sorting the edges beforehand, and then building a set of trees which you later reconnect. You build each tree by connecting the cheapest two vertices in your graph which are not already in the same tree, and repeat until you have them all. Both algorithms are guaranteed to produce a minimum spanning tree in linearithmic time. (If your graph is unweighted, then the preprocessing step in kruskal could be removed, and all edge selection in prim could be removed, and we would have a linear time algorithm. This is clearly optimal because it would take linear time to even read the input).

Answer 2

I think a depth first search is enough, which is $\mathcal{O}(|V| + |E|)$. Both Prim's algorithm and Kruskal's algorithm in fact return a minimum spanning tree, but it seems that you only ask to return any spanning tree.