Найдите цикл в неориентированном графе (буст) и верните его вершины и ребра

Question

Мне нужны функции, которые находят цикл в неориентированном графе (повышение) и возвращают его вершины и ребра. Нужно только вернуть вершины / ребра одного цикла в графе. Мой вопрос - каков наилучший способ сделать это с помощью Boost? У меня нет опыта его использования.

Answer 1

Я не знаю, Boost, но здесь - ответ С.О. на концептуальном уровне:

Вот мое предположение: пройтись по графику с помощью BFS. На каждом узле отметьте его «глубину» и добавьте ссылку на «родитель» (должен быть только один, даже если есть много циклов) Как только вы обнаружите, что ссылка от A до B создает цикл (потому что B уже окрашен), тогда: 1) Вернитесь назад от A к корню, сохраните ребра / вершины по пути. 2) Вернитесь назад от B обратно к корню, сохраните ребра / вершины по пути. 3) Добавить A, B, AB 4) «Сортировка» для восстановления правильного порядка. Попробуйте использовать LIFO (стек) для 1) и FIFO для 2)

Надеюсь, это поможет.

Answer 2

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

Answer 3

Если вы хотите найти цикл a , то сначала используйте поиск по глубине. Посетитель DFS имеет функцию back_edge. Когда это называется, у вас есть преимущество в цикле. Затем вы можете пройти по карте предшественника, чтобы восстановить цикл. Обратите внимание:

• Есть функция strong_components, чтобы найти, ну, сильные компоненты
• Найти все циклы, в отличие от цикла, гораздо сложнее, и я считаю, что Boost.Graph в настоящее время не имеет реализации для этого