Допустим, у нас есть неориентированный граф G (E, V) и данная вершина v. Я хочу найти минимальное остовное дерево T, чтобы степень (v) = k в T.
- Я рассмотрел поиск всех смежных вершин v в G.
- find q (q = степень (v)) Минимальные остовные деревья (1, начиная с каждой вершины, соседней с v) с использованием модифицированного Крускала.
- Конвертируйте эти MST в супервертики, и теперь у меня есть V и степени (v) MST
- Теперь соедини все вышеперечисленное, используя модифицированный kruskal, чтобы убедиться, что степень (v) = k
Может ли кто-нибудь подтвердить, что мой алгоритм найдет правильный результат? может предложить другой подход?