Нахождение всех циклов в ориентированном графе

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

Запустите в узле X и проверьте на все дочерние узлы (родительские и дочерние узлы эквивалентны если неориентированный). Mark те дочерние узлы, как являющиеся детьми X. От любого такого дочернего узла A, отметьте, это - дети того, чтобы быть детьми A, X', где X' отмечен как являющийся 2 шагами далеко.). Если Вы позже поражаете X и отмечаете его как являющийся ребенком X'', который означает X, находится в 3 циклах узла. Отслеживание в обратном порядке к он - родитель, легко (как есть, алгоритм не имеет никакой поддержки этого так, Вы нашли бы, какой бы ни родитель имеет X').

Примечание: Если граф является неориентированным или имеет какие-либо двунаправленные края, этот алгоритм становится более сложным, предполагая, что Вы не хотите пересекать тот же край дважды для цикла.

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

1. , как Вы определяете следующий допустимый маршрут
2. , как Вы определяете, использовалась ли точка
3. , как Вы стараетесь не пересекать ту же точку снова

проблема 1) Использование шаблон итератора для давания возможность итерации результатов маршрута. Хорошее место для помещения логики для получения следующего маршрута является, вероятно, "moveNext" итератора. Для нахождения допустимого маршрута это зависит от структуры данных. Для меня это была sql таблица, полная возможностей допустимого маршрута, таким образом, я должен был создать запрос для получения допустимых мест назначения, учитывая источник.

проблема 2) Нажатие каждый узел, поскольку Вы находите их в набор, поскольку Вы получаете их, это означает, что Вы видите, "загибаете" ли Вы по точке очень легко путем опроса набора, Вы создаете на лету.

проблема 3), Если в какой-либо точке Вы видите, Вы загибаете, можно вытолкать вещи от набора и "создать резервную копию". Затем от той точки пытаются "продвинуться" снова.

Взлом: если Вы используете SQL-сервер 2008, там, некоторые новые вещи "иерархии", которые можно использовать для быстрого решения этого при структурировании данных в дереве.

Поиск в глубину с отслеживанием в обратном порядке должен работать здесь. Сохраните массив булевых значений для отслеживания то, посетили ли Вы узел прежде. Если у Вас заканчиваются новые узлы для движения в (не поражая узел, Вы уже были), то просто отслеживают в обратном порядке и пробуют другое ответвление.

DFS легко реализовать, если у Вас есть список смежности для представления графика. Например, прил = {B, C} указывает, что B и C являются детьми A.

, Например, псевдокодируйте ниже. "запуск" является узлом, с которого Вы запускаете.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Вызов вышеупомянутая функция с узлом запуска:

visited = {}
dfs(adj,start,visited)

Я нашел эту страницу в своем поиске, и, поскольку циклы не такие же, как сильно связанные компоненты, я продолжил поиск и, наконец, нашел эффективный алгоритм, который перечисляет все (элементарные) циклы ориентированного графа. Это от Дональда Б. Джонсона, и этот документ можно найти по следующей ссылке:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

A Реализацию java можно найти в:

http://normalisiert.de/code/java/elementaryCycles.zip

Демонстрацию алгоритма Джонсона в Mathematica можно найти здесь , реализацию можно скачать справа ( «Скачать код автора» ).

Примечание: на самом деле существует множество алгоритмов для решения этой проблемы. Некоторые из них перечислены в этой статье:

http://dx.doi.org/10.1137/0205007

Согласно статье, алгоритм Джонсона является самым быстрым.

Я наткнулся на следующий алгоритм, который кажется более эффективным, чем алгоритм Джонсона (по крайней мере, для больших графов). Однако я не уверен в его эффективности по сравнению с алгоритмом Тарджана.
Кроме того, пока что я проверил его только для треугольников. Если интересно, пожалуйста, посмотрите "Arboricity and Subgraph Listing Algorithms" by Norishige Chiba and Takao Nishizeki (http://dx.doi.org/10.1137/0214017)