Дан направленный граф, задан структурно т.е. вершина может содержать ссылки на другие вершины.
Нужно найти все циклы в графе.
Что можно посмотреть на эту тему?
N>Дан направленный граф, задан структурно т.е. вершина может содержать ссылки на другие вершины. N>Нужно найти все циклы в графе. N>Что можно посмотреть на эту тему?
Наверное, нужно начать с определения цикломатического числа и фундаментального цикла.
А вообще-то уже неоднократно обсуждали: http://rsdn.org/forum/alg/110876.flat
Здравствуйте, nen777w, Вы писали:
N>Дан направленный граф, задан структурно т.е. вершина может содержать ссылки на другие вершины. N>Нужно найти все циклы в графе.
Можно начать с поиска компонент сильной связности, и потом решать задачу для каждой из них.
N>Что можно посмотреть на эту тему?
Здравствуйте, nen777w, Вы писали:
N>Дан направленный граф, задан структурно т.е. вершина может содержать ссылки на другие вершины. N>Нужно найти все циклы в графе. N>Что можно посмотреть на эту тему?
1. Поиск в глбуину.
2. Думаю, волновой алгоритм подойдёт в котором за один шаг будет "окрашиваться" веришина в некий цвет который соответствует цвету исходной вершины. На след. шаге просто раскрашиваем смежные вершины проверяя текущий цвет, если он совпал, то вот он, цикл и нужно просто востановить маршрут.
Здравствуйте, Kernan, Вы писали:
K>Поиск в глбуину.
Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, Kernan, Вы писали:
K>>Поиск в глбуину.
Q>Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Для непримитива надо теоримы из ТГ смотреть и придумывать что-то. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.
Здравствуйте, Kernan, Вы писали:
K>Для непримитива надо теоримы из ТГ смотреть и придумывать что-то. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.
Под примитивом я имел в виду базовую процедуру-кирпичик. Например, предложенный выше поиск компонент сильной связности использует (дважды) обход в глубину.
Здравствуйте, nen777w, Вы писали:
N>Дан направленный граф, задан структурно т.е. вершина может содержать ссылки на другие вершины. N>Нужно найти все циклы в графе. N>Что можно посмотреть на эту тему?
На настоящий момент самым эффективным алгоритмом является алгоритм Tiernan-а
При наличии бесконечной памяти на компьютере, есть вероятность не дожить до того счастливого момента, когда будут найдены все циклы даже для небольшого графа с числом вершин ~100
Программная реализация имеется в boost::graph в tiernan_all_cycles.hpp
