Нахождение мостов в графе C ++ (BOOST)?
Я читал библиотеку BOOST и заметил, что у них нет алгоритма для нахождения мостов в графе, у них есть алгоритм для нахождения точек сочленения. Есть ли в любом случае это может быть сделано эффективно?
У меня есть идея:
1. Используйте BOOST, чтобы найти точки сочленения
2. Используя out_edges, найдите все ребра, прикрепленные к каждой точке сочленения
3. удалите их и вычислите число подключенных компонентов (я предполагаю, что мой график изначально полностью связан), если его больше 1, я добавляю это ребро к мостам.
ВОПРОС: Необходимо ли прикреплять мосты к точкам сочленения? Я просто предположил, что они есть, не мог найти ничего, кроме сети.
Я также хотел бы идею, как подойти к этому.
Мой другой подход был бы более наивным и взял бы O (v * (V + E)), что очень плохо.
Решение
Звучит немного медленно с переписыванием всего графика. Вы должны проверить, считает ли Boost односвязную вершину как точку сочленения. (Если нет, это немного усложняет ситуацию).
Теперь совершенно очевидно, что мост должен быть ребром между двумя точками сочленения, но не все ребра между точками сочленения обязательно являются мостами. Рассмотрим цепочку из 4 точек сочленения, соединенных 3 ребрами: A-b-c-D. Теперь добавьте узел e, подключенный к b и c. Внешние два моста остаются мостами, и поэтому все 4 исходных узла остаются точками сочленения, но средний узел больше не является мостом.
Это означает, что у нас есть необходимое, но недостаточное дополнительное условие: оба узла ребра должны быть точками сочленения. Вот где небольшое осложнение вступает; если Boost не считает односвязные узлы точками артикуляции, вы должны обращаться с ними специально. Но это все еще просто; этот край обязательно является мостом.
Это дополнительное условие достаточно эффективно в плотных графах, так как большинство узлов не будут точками сочленения. В результате вы отбираете большинство подходящих ребер, прежде чем пытаться изменить график. Во-вторых, вам не нужно проверять количество компонентов результирующего измененного графа. Вам просто нужно проверить, соединены ли две точки сочленения после того, как вы обрезаете край, связывая их напрямую.
Другие решения
Существует гораздо более простой способ, когда вы понимаете, что если двусвязный компонент содержит только одно ребро, то это ребро является мостом. Это очень легко реализовать с помощью boost (http://www.boost.org/doc/libs/1_58_0/libs/graph/example/biconnected_components.cpp):
- Рассчитать двусвязные компоненты
- Создайте счетчик ребер для каждого компонента. Итерация по всему ребру и увеличение базового счетчика ребер соответствующего компонента
- Повторите итерацию по всем ребрам и проверьте, равен ли счетчик ребер соответствующего компонента 1, если это так, то это ребро является мостом.