Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Проверить структуру на цикл

Автор: xTr1m 14.11.2012, 19:07

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

Код


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

Автор: feodorv 14.11.2012, 20:14

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

Автор: xTr1m 15.11.2012, 13:52

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

Автор: xvr 15.11.2012, 14:03

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

)

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

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

Код


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

Для нахождения циклов применяют более продвинутые алгоритмы - алогритм http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm (пожалуй самый известный). Ну и еще

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

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

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