crossplatform.ru

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

 
Ответить в данную темуНачать новую тему
> graph biconnected components, построение двусвязного графа
efg
  опции профиля:
сообщение 27.3.2012, 22:01
Сообщение #1


Студент
*

Группа: Участник
Сообщений: 48
Регистрация: 6.5.2011
Пользователь №: 2658

Спасибо сказали: 2 раз(а)




Репутация:   0  


пример посмотрел, компилить - компилится. что дальше делать - не пойму. нужно достроить граф, чтобы обеспечить двусвязность.
Прикрепленное изображение

как можно использовать эту информацию? понятно, что эти articulations points нужно с чем-нибудь соединить, но как, чтобы по-хорошему всё было? покороче и покрасивше. у меня граф взвешенный, кстати, в отличие от примера

Сообщение отредактировал efg - 27.3.2012, 22:09
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 28.3.2012, 8:54
Сообщение #2


Профессионал
*****

Группа: Модератор
Сообщений: 1586
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


это и так ненаправленный (undirectedS) граф. читай документацию на библиотеку:
http://www.boost.org/doc/libs/1_49_0/libs/...-and-undirected
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
efg
  опции профиля:
сообщение 3.6.2012, 4:52
Сообщение #3


Студент
*

Группа: Участник
Сообщений: 48
Регистрация: 6.5.2011
Пользователь №: 2658

Спасибо сказали: 2 раз(а)




Репутация:   0  


да, кстати. совещались на лоре, алгоритм примерно такой:

1) Нашли точки сочленения
2) Рассматриваем граф без них
3) Сжимаем каждую связную компоненту в вершину
4) Находим минимальное остовное дерево
5) Восстанавливаем по пунктам 2-4, что надо было сделать с исходным графом

Сначала достроить до односвязного: разбить на компоненты -> сжать в вершины -> минимальное остовное дерево — получим набор дополнительных ребер (*).
Теперь изначальных алгоритм нормально отработает. Получится двусвязный граф. Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 25.6.2019, 22:39