Мне интересно найти общее количество циклов и длины циклов в связанном неориентированном графе. Могу ли я использовать DFS? Или DFS может найти только один цикл? Любой код определенно поможет.Поиск общего числа циклов и длины цикла
Взгляните на следующей ссылке:
Точно то, что я разместил. Извините, я не получил новое сообщение. – colithium
, как указано в цитированном pdf: Число циклов может быть экспоненциальным по числу узлов. Используя простой DFS, каждый цикл найден с использованием одного временного шага, что приводит к экспоненциальному времени работы. Если это становится проблемой (на плотном графике даже для менее 100 узлов), нужно использовать более сложный алгоритм. Я имел в виду, что он существует. – eci
Какой язык вы работаете? И я думаю, что один из них должен быть BFS =) – colithium
Также имейте в виду, что количество циклов на графике умеренного размера может быть ОГРОМНЫМ. – colithium
Я хочу использовать Java – 2009-06-30 14:04:32