ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Dashkovsky                    2:5002/46.4    11 Dec 2002  23:56:04
 To : Vlad
 Subject : Графы с циклами
 -------------------------------------------------------------------------------- 
 

 11 Дек 02 00:53, you wrote to all:
  v> Кто нибудь встречал инфу или алгоритмы по работе с графами,
  v> содержащими циклы, в частности интересует нахождение оных циклов
 
 Чтобы найти все циклы в графе надо:
 1. Hайти все базовые
 2. перебрать все комбинации базовых, т.е. там что-то типа построений сочетаний,
 решений будет очень много, но программа будет тратить время уже не на поиски, а
 на вывод решений в файл или на экран
 
 Чтобы найти все базовые делается обычный обход графа вглубину:
 
 1. Берём стартовую вершину
 2. Смотрим есть ли она в стеке, если есть то 3.
 3. тогда из стека извлекаем всю цепочку от первого вхождения и это будет
 базовый цикл
 4. если её всётаки в стеке нету, тогда ложим её в стек и берём первую
 попавшуюся исходящёю из неё и повторяем 2., причём именно первую, т.к. все
 исходящие перебираем в определённом порядке(причём варианта 2 - либо сортировать
 вершины по какому-то признаку, но ИМХО это лишнее, можно использовать тот
 порядок, в котором заданы вершины)
 5.если взять нечего, тогда откатываемся на верх из стека и берём следующую
 вершину.и снова п. 2.
 6. выход из цикла в том случае если идти уже некуда и в стеке пусто.
 
 Т.о. смысл такой - идём вглубь, пока можем, как только не смогли - откатываемся
 наверх, берём следующую исходящую дугу, за той, по которой мы приплыли и снова
 идём вглубь, причём все циклы, на которые мы натыкаемся выносим в список базовых
 циклов.
 
 Зы. Если что не понятно - спрашивай.
 
 Andrey
 
 ... Большому кораблю - большая торпеда.
 --- GoldED+/386 1.1.4.7
  * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Графы с циклами   vlad   11 Dec 2002 01:53:35   Графы с циклами   Andrey Dashkovsky   11 Dec 2002 23:56:04