VPF::Проверить структуру на цикл - Форум программистов

xTr1m

Дата 14.11.2012, 19:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 692
Регистрация: 9.2.2005
Где: Москва

Репутация: 1
Всего: 1

Доброго времени суток. Есть класс:

Код


class CRelation
{
    CObject *related;
    CObject *relating;
}
В системе есть много объектов, определяющих таким образом древовидную структуру. необходимо написать алгоритм, позволяющий находить циклы в такой структуре.
Пока в голову лезут всякие глупые вещи в лоб, но уже на начальном этапе реализации вижу, что работает долго. Таких объектов-связей около 50000. Буду благодарен за подсказку в каком напрвлении двигаться.

feodorv

Дата 14.11.2012, 20:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Я бы сделал простой список указателей всех объектов, в начале пустой, возможно, с сортировкой по значению указателя (для быстрого поиска).
Затем обошёл бы всё дерево, от корня, добавляя в список указатель на очередную структуру. Вот если этот указатель уже находится в списке, то имеем цикл.

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

xTr1m

Дата 15.11.2012, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 692
Регистрация: 9.2.2005
Где: Москва

Репутация: 1
Всего: 1

Тут забыл конечно уточнить, что один и тот же элемент может встречаться в разных ветках дерева. Но примерно так и сделал. То есть обошел каждую ветку вглубь, запоминая какие элементы уже встречались. И если дубль, то да - цикл. Спасибо.

xvr

Дата 15.11.2012, 14:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(feodorv @ 14.11.2012, 20:14

)

Затем обошёл бы всё дерево, от корня, добавляя в список указатель на очередную структуру. Вот если этот указатель уже находится в списке, то имеем цикл.

Не обязательно, это может быть DAG -

Код


 a -> b -> c
 |---------^

Для нахождения циклов применяют более продвинутые алгоритмы - алогритм Тарьяна (пожалуй самый известный). Ну и еще

DFS алгоритм -
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
http://www.personal.kent.edu/~rmuhamma/Alg...depthSearch.htm

Еще немного -
http://www.ics.uci.edu/~eppstein/161/960220.html
http://dutta.csc.ncsu.edu/csc791_spring07/...its_johnson.pdf
http://en.wikipedia.org/wiki/Strongly_connected_components

Ну и Топологическая Сортировка графа тоже может помочь

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »