Здравствуйте, гость ( Вход | Регистрация )
efg | Дата 3.6.2012, 4:52 | |
да, кстати. совещались на лоре, алгоритм примерно такой: 1) Нашли точки сочленения 2) Рассматриваем граф без них 3) Сжимаем каждую связную компоненту в вершину 4) Находим минимальное остовное дерево 5) Восстанавливаем по пунктам 2-4, что надо было сделать с исходным графом Сначала достроить до односвязного: разбить на компоненты -> сжать в вершины -> минимальное остовное дерево — получим набор дополнительных ребер (*). Теперь изначальных алгоритм нормально отработает. Получится двусвязный граф. Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности. |
||
Iron Bug | Дата 28.3.2012, 8:54 | |
это и так ненаправленный (undirectedS) граф. читай документацию на библиотеку: http://www.boost.org/doc/libs/1_49_0/libs/...-and-undirected |
||
efg | Дата 27.3.2012, 22:01 | |
пример посмотрел, компилить - компилится. что дальше делать - не пойму. нужно достроить граф, чтобы обеспечить двусвязность. как можно использовать эту информацию? понятно, что эти articulations points нужно с чем-нибудь соединить, но как, чтобы по-хорошему всё было? покороче и покрасивше. у меня граф взвешенный, кстати, в отличие от примера |
||
Просмотр темы полностью (откроется в новом окне) | ||
Текстовая версия | Сейчас: 28.3.2024, 18:24 |