crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )


  Ответ в graph biconnected components
Введите ваше имя
Подтвердите код

Введите в поле код из 6 символов, отображенных в виде изображения. Если вы не можете прочитать код с изображения, нажмите на изображение для генерации нового кода.
 

Опции сообщения
 Включить смайлы?
Иконки сообщения
(Опционально)
                                
                                
  [ Без иконки ]
 


Последние 10 сообщений [ в обратном порядке ]
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 нужно с чем-нибудь соединить, но как, чтобы по-хорошему всё было? покороче и покрасивше. у меня граф взвешенный, кстати, в отличие от примера
Просмотр темы полностью (откроется в новом окне)
RSS Текстовая версия Сейчас: 28.3.2024, 18:24