Исключить из графа все вершины не входящие в выборку, заменив на ребра со сложенным весом. Т.е. допустим есть вершина А, ребра AB=1, AC=1, AD=2. Вершина и ребра заменяются на ребра: BC=2, BD=3, CD=3
Затем найти минимальное остовное дерево. Можно взять алгоритм Краскала, описание есть на вики:
https://ru.wikipedia.org/wiki/Алгоритм_Краскала