Использование ребер из A не позволит вам получить фактическое минимальное остовное дерево, если ребра в A не гарантированно принадлежат MST.
Однако, учитывая набор A, вы можетенайдите MST, который соединяет все остальные вершины с A.
. Вы не гарантируете, что ребра в A образуют один связанный компонент, поэтому я предполагаю, что они этого не делают.
В этом случае использование алгоритма Прима является плохой идеей, поскольку алгоритм Прима предполагает, что на каждом шаге вы добавляете грань между действительным MST и точкой, которой нет в MST.Поскольку «MST», образованный A, может быть несмежным, это нарушает допущения алгоритма Прима.
Вместо этого используйте алгоритм Крускала .Он добавляет ребра в «набор MST», рассматривая ребра в порядке их длины, всегда сначала выбирая самое короткое ребро.Если оба конца ребра уже находятся в наборе MST, то ребро отклоняется.Если в наборе MST только одно ребро, то новое ребро добавляется в множество MST.
Вы можете реализовать алгоритм следующим образом:
KRUSKAL(G,A):
mst_set = ∅
for each vertex v ∈ G.V:
MAKE-SET(v)
for each edge (u,v) in A:
mst_set = mst_set ∪ {(u,v)}
UNION(u,v)
for each edge (u, v) in G.Edges ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
mst_set = mst_set ∪ {(u, v)}
UNION(u, v)
return mst_set
где MAKE-SET,Операции UNION и FIND-SET являются частью структуры данных с непересекающимся набором.