Каков правильный порядок вершин алгоритма Prim с этого графика?

Question

Я хочу знать порядок вершинной алгоритма Прима из этого графика:

Мой ответ {a,c,b,e,f,g,d}, а другие говорили: {a,c,b,e,d,f,g} или {a,c,d,e,b,f,g}.

Какой ответ правильный?

Answer 1

Правильно!

Минимальное покрывающее дерево, если мы выбираем начать с a выглядит следующим образом:

a -> c -> b-> e -> f -> g 
    | 
    -> d 

И для того, что мы добавляем вершины к дереву, как вы выяснили, {a,c,b,e,f,g,d}.