Создание связующего дерева с использованием BGL

Question

У меня есть график BGL и я хочу создать остовное дерево, используя BGL.

Начиная с указанной вершины, я хочу добавить кратчайший край моего графа, который соединяется с этой вершиной.С этого момента я хочу всегда выбирать самое короткое ребро, которое связано с графом, который существует до сих пор.

Итак, я хочу добавить ограничение, что каждое новое ребро должно быть связано с графом уже во время пребыванияс критерием связующего дерева, что циклов нет.

Было бы не сложно сделать это вручную;но поскольку я хочу кое-что узнать о BGL, я бы хотел знать, какой алгоритм лучше всего подходит для моей задачи.

Answer 1

Звучит так, как будто вы выращиваете дерево, начиная с указанной вами вершины, добавляя самый легкий край, соединяющий вершину в вашем дереве с вершиной, которой нет в вашем дереве.Если это так, вы реализуете алгоритм Prim, который дает вам MST.Это хорошо описано в главе MST «Алгоритмы» Cormen, Leiserson, Rivest & Stein.

(я говорю «звучит как», потому что утверждение «кратчайшее ребро, связанное с графом, существующим до сих пор»немного расплывчато.)

Answer 2

Это алгоритм Prim: http://en.wikipedia.org/wiki/Prim%27s_algorithm

Вы получите минимальное связующее дерево!

Не уверен, что вы будете полагаться на BGL, но в любом случае в этой идее сложно найти «минимальное преимущество»: посмотрите на псевдокод на странице википедии, чтобы увидеть, как это можно сделать, используя двоичная куча. Для большей сложности вам понадобится куча Фибоначчи.