Створення дерева, що використовується, за допомогою BGL - c ++, алгоритму, прискорення, графа, буст-графа

У мене є графік BGL і я хочу створити розтягнуте дерево за допомогою BGL.

Починаючи з вказаної вершини, я хочу додатинайкоротший край мого графіка, який з'єднується з цією вершиною. З цього моменту я хочу завжди вибрати найкоротший край, який з'єднується з існуючим на сьогодні графіком.

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

Це було б не важко зробити вручну, але оскільки я хочу дізнатися щось про BGL, я хотів би знати, який алгоритм найкраще відповідає моїй проблемі.

Відповіді:

Здається, що ти росте дерево, починаючиз вказаною вершиною, додавши найлегший край, який з'єднує вершину у вашому дереві, до вершини, яка "не у вашому дереві. Якщо це так, ви реалізуєте алгоритм Prim", який дає вам MST. Це чудово описано в главі MST "Алгоритми" Cormen, Leiserson, Rivest & Stein.

(Я кажу "звучить як", оскільки вислів "найкоротший край, який з'єднується з наявним на сьогодні графіком" є трохи розпливчастим.)

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

Ви отримаєте мінімальну пролітну ялинку!

Не впевнений, якщо ви будете накладати з ним багато BGL, алеу будь-якому разі, що в цій ідеї важко - знайти "мінімальний край": подивіться псевдо-код на сторінці Вікіпедії, щоб побачити, як це можна зробити за допомогою двійкової купи. Для кращої складності вам знадобиться купа Фібоначчі.