| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Матрица связности в матрицу достижимости |
| Автор: Sartorius 20.3.2007, 10:58 |
Всем привет.  Не подскажете алгоритм преобразования матрицы связности в матрицу достижимости. Очень хотелось бы на C/C++. ЗЫ гугл и поиск по форуму ничего не дал((( ЗЗЫ ах да. Графы неориентированные и содержат циклы. В общем задача по сути состоит в том, что бы для данного графа выделить множество его связных подграфов. |
| Автор: MBo 20.3.2007, 13:35 |
| Обход в глубину (DFS) поможет получить набор помеченных связных компонентов. Помечаем все вершины нулевой меткой. Начинаем с первой вершины, выполняем DFS, помечая единицей. Если осталиcь непомеченные вершины, следуюший связный компонент помечаем двойкой (или номером вершины, с которой начали обход) и т.д. Получим одномерный массив, для неорграфов матрица - избыточна |
| Автор: comp 20.3.2007, 13:45 |
| Ну и, наверное, лучьше в ширину обходить... |
| Автор: Sartorius 20.3.2007, 13:48 |
| MBo, спасибо)) Это решение очевидно, я думал может кто даст ссылку на какой нить оптимизированный общепринятый алгоритм, а еще лучше на готовую реализацию... |
| Автор: MBo 20.3.2007, 14:03 |
| >какой нить оптимизированный общепринятый алгоритм для орграфов есть метод с возведением матрицы смежности в степень, Уоршалла и т.д., но они намного тяжелее, ведь и задача для орграфов сложнее. А обходы делаются за линейное время, и реализации найти совсем нетрудно. Модификация минимальна - вместо обычного флага "помечен" - число, идентификатор группы. |
| Автор: Sartorius 20.3.2007, 14:12 |
| Ок. Всем спасибо. буду простым обходом делать. |