У меня есть неориентированный граф, который содержит несколько узлов типа A и несколько узлов типа B. Мне нужно создать граф (не обязательно связанный глобально), чтобы каждый узел типа A был связан (через любое количество ребер) хотя бы с одним узел типа В. Все ребра имеют веса. Я хочу создать MST, удовлетворяющий этому условию, но не могу придумать лучший алгоритм для этого.
Позвольте мне уточнить. Если у меня есть один узел типа B, все, что мне нужно сделать, это просто создать MST в обычном режиме. Но поскольку у меня более одного узла типа B, может существовать более эффективный способ создания MST, который не потребует от меня соединения всех вершин в графе. Например, я могу игнорировать узел типа B, если это не самое дешевое соединение с любым узлом типа A. В конце концов, у меня вполне может быть граф с несколькими несвязанными MST, а не с одним.
Каков наилучший алгоритм для этого?
