Здравствуйте.
у меня задача проверить граф на ацикличность.в файл выводить самый первый цикл который найдем.
Проблема в том что её надо решать именно поиском в ширину.какой будет алгоритм?? запускать поиск в ширину из всех вершин действительно неэффективно
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, KAO_09, Вы писали:
KAO>>у меня задача проверить граф на ацикличность.в файл выводить самый первый цикл который найдем.
KAO>>Проблема в том что её надо решать именно поиском в ширину.какой будет алгоритм?? запускать поиск в ширину из всех вершин действительно неэффективно
C>Так вроде стандартная задача на динамическое программирование.
C>Для направленного графа:
C>Изначально каждая вершина графа не помечена. Берём произвольную вершину, отмечаем её цифрой "1". Затем все связанные с ней вершины отмечаем цифрой "2". Связанные с ними вершины — цифрой "3" и так далее. Если у какой-то помеченной вершины есть связь с другой уже помеченной вершиной, то мы нашли цикл. Дальше просто идём по цифрам назад.
Это для неориентированного. Кроме того, в худшем случае в конце получим множество непомеченных вершин (попался лес). В этом остатке вершин запускаем тот же алгоритм и так проверяем все компоненты связности, пока они не кончатся.
Для ориентированного можно добавить вершину с номером -1, из нее провести ребра во все остальные вершины, и начать с нее топологическую сортировку.
Ну и по соотношению числа вершин и ребер предварительно проверить можно.
Здравствуйте, KAO_09, Вы писали:
Действительно не эффективно
Поэтому надо использовать обход в глубину. Откуда взялось требование с BFS?
