CODEWITHSUNDEEP
algorithmgraph-theoryminimum-spanning-tree
John Lexus
John Lexus

Reputation: 3646

Creating several minimum spanning trees with specific requirements

I have an undirected graph that contains several nodes of type A and some nodes of type B. I need to create a graph (not necessarily connected globally) such that each type A node is connected (through any number of edges) to at least one type B node. All edges have weights. I want to create an MST that fulfills this condition, but I cannot think of the best algorithm to do that.

Let me clarify. If I have one type B node, then all I need to do is just create an MST normally. But since I have more than one type B node, there may be a more efficient way to create an MST that will not require me to connect all the vertices in the graph. For example, I may choose to ignore a type B node if it's not the cheapest connection to any type A node. In the end, I may well have a graph that has several disconnected MSTs, not just one.

What is the best algorithm for doing this?

Upvotes: 1

Views: 608

Answers (1)

Prune
Prune

Reputation: 77880

Iterate through this process:

  1. Find the least expensive connection to connect a type A node to a type B node.
  2. Change that A-node's label to type B.
  3. Repeat until there are no more A nodes.

Note one important property of your problem: any minimal solution must have each A node connected to exactly one B node.

Upvotes: 1

Related Questions