Алгоритм нахождения минимального остовного дерева выбранных вершин
Можно использовать алгоритм Прима или алгоритм Крускала, чтобы найти минимальное остовное дерево / граф совокупности вершин / узлов и ребер / связей. Однако мне нужен алгоритм, который находит минимальный остовный граф этой коллекции, но полученный граф должен включать только произвольно выбранные узлы, а не все узлы. Это нормально, если полученный граф включает в себя больше узлов, чем нужно.
Существует ли такой алгоритм? Возможно, можно было бы просто использовать алгоритм Прима (или Крускала) после изменения графа, чтобы включить только необходимые узлы? Но я не уверен, как изменить график, чтобы сохранить его связность.
Например, скажем, у нас есть начальный граф в форме ромба (со стоимостью ссылок в скобках):
A
(2)/ \(1)
B C
(2)\ /(5)
D
Теперь мы произвольно решаем, что нужны только узлы A и D. Если бы мы начали с А, мы все равно хотели бы, чтобы он пошел левым путем, потому что ((2 + 2) <(1 + 5)).
Скажем, мы немного изменим график:
A
(2)/ \(1) (2)
B C ------E
(2)\ /(5)
D
Если мы решим, что нужны только узлы A, D и E, мы поймем, что путь с минимальной стоимостью не обязательно является тем, который имеет наименьшее количество ссылок. Взятие A - B - D и A - C - E стоит 7, но A - C - D и C - E стоит 8.