Графы с циклами

From

Andrey Dashkovsky (2:5002/46.4)

To

Vlad

Date

2002-12-11T22:56:04Z

Area

RU.ALGORITHMS

Hello vlad.

11 Дек 02 00:53, you wrote to all:


 v> Кто нибудь встречал инфу или алгоритмы по работе с графами,
 v> содержащими циклы, в частности интересует нахождение оных циклов

Чтобы найти все циклы в графе надо:
1. Найти все базовые
2. перебрать все комбинации базовых, т.е. там что-то типа построений сочетаний,
решений будет очень много, но программа будет тратить время уже не на поиски, а
на вывод решений в файл или на экран

Чтобы найти все базовые делается обычный обход графа вглубину:

1. Берём стартовую вершину
2. Смотрим есть ли она в стеке, если есть то 3.
3. тогда из стека извлекаем всю цепочку от первого вхождения и это будет
базовый цикл
4. если её всётаки в стеке нету, тогда ложим её в стек и берём первую
попавшуюся исходящёю из неё и повторяем 2., причём именно первую, т.к. все
исходящие перебираем в определённом порядке(причём варианта 2 - либо сортировать
вершины по какому-то признаку, но ИМХО это лишнее, можно использовать тот
порядок, в котором заданы вершины)
5.если взять нечего, тогда откатываемся на верх из стека и берём следующую
вершину.и снова п. 2.
6. выход из цикла в том случае если идти уже некуда и в стеке пусто.

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

Зы. Если что не понятно - спрашивай.

Andrey

... Большому кораблю - большая торпеда.
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)