When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

typedeftemplate's blog

By typedeftemplate, history, 3 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Before running Kruskal's algorithm, join vertices $$$v_1,\ldots,v_n$$$ in the union-find data structure.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

[Deleted]