Hi all,
While learning about minimum spanning trees a while back, I encountered the following problem:
Given a connected undirected graph $$$G = (V, E)$$$ and a subset of vertices $$$S = {v_1, v_2, \ldots, v_n}$$$, find a forest in which each vertex $$$v \in V \setminus S$$$ is connected to exactly one vertex of $$$S$$$ such that this forest has minimum total length (sum of edge weights).
I vaguely remember that the solution to this problem involved reducing the problem to a minimum spanning tree problem. In particular, a graph $$$G'$$$ was constructed in which one could run the minimum spanning tree on $$$G'$$$ in order to retrieve the final answer. However, I've forgotten the solution, and I'm wondering if someone can explain the solution to me.
I think that one can just keep edges of the form $$$(u, v)$$$ where $$$u$$$ is in $$$S$$$ and $$$v$$$ isn't. From here, I think we can just run an MST algorithm on the graph $$$G'$$$, but I'm not entirely sure if this is correct.
Thanks
Before running Kruskal's algorithm, join vertices $$$v_1,\ldots,v_n$$$ in the union-find data structure.
Imagine there is an invisible node $$$P$$$ connected with $$$v_1,v_2,...,v_n$$$ already, then you can do any sort of MST algo.
If you use Kruskal, you just have to merge $$$v_1,v_2,...,v_n$$$ in the union data structure as they are already connected together with $$$P$$$.
If you use Prim, you should put $$$v_1,v_2,...,v_n$$$ in the queue and set them as connected to the main part of the tree.
[Deleted]