 |
|
|
 
|
|
Матрица связности в матрицу достижимости, как преобразовать? 
| Sartorius |
|
|||
 Эксперт  Профиль Группа: Завсегдатай Сообщений: 1568 Регистрация: 18.7.2006 Где: Ivory tower Репутация: 1 Всего: 37 |
Всем привет.
 Не подскажете алгоритм преобразования матрицы связности в матрицу достижимости. Очень хотелось бы на C/C++. ЗЫ гугл и поиск по форуму ничего не дал((( ЗЗЫ ах да. Графы неориентированные и содержат циклы. В общем задача по сути состоит в том, что бы для данного графа выделить множество его связных подграфов. Это сообщение отредактировал(а) Sartorius - 20.3.2007, 11:21 |
|||
|
||||
Загрузка ...
| MBo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 5 Всего: 18 |
Обход в глубину (DFS) поможет получить набор помеченных связных компонентов.
Помечаем все вершины нулевой меткой. Начинаем с первой вершины, выполняем DFS, помечая единицей. Если осталиcь непомеченные вершины, следуюший связный компонент помечаем двойкой (или номером вершины, с которой начали обход) и т.д. Получим одномерный массив, для неорграфов матрица - избыточна |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: 1 Всего: 1 |
Ну и, наверное, лучьше в ширину обходить...
|
|||
|
||||
| Sartorius |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 1568 Регистрация: 18.7.2006 Где: Ivory tower Репутация: 1 Всего: 37 |
MBo, спасибо)) Это решение очевидно, я думал может кто даст ссылку на какой нить оптимизированный общепринятый алгоритм, а еще лучше на готовую реализацию...
|
|||
|
||||
| MBo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 5 Всего: 18 |
>какой нить оптимизированный общепринятый алгоритм
для орграфов есть метод с возведением матрицы смежности в степень, Уоршалла и т.д., но они намного тяжелее, ведь и задача для орграфов сложнее. А обходы делаются за линейное время, и реализации найти совсем нетрудно. Модификация минимальна - вместо обычного флага "помечен" - число, идентификатор группы. |
|||
|
||||
| Sartorius |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 1568 Регистрация: 18.7.2006 Где: Ivory tower Репутация: 1 Всего: 37 |
Ок. Всем спасибо. буду простым обходом делать.
Это сообщение отредактировал(а) Sartorius - 20.3.2007, 14:13 |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0685 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |