Алгоритм поиска кратчайших циклов в ориентированном графе

Question

Самый короткий цикл - это число с минимальным количеством ребер.

Например, для графа:

Самые короткие циклы: ACDA, DABD

Если бы я должен был найти один короткий цикл, я бы просто запустить BFS на каждой вершине и следить за наименьшим циклом. Но я не знаю, как перечислить все наименьшие циклы.

Существует аналогичный SO question при перечислении минимальных циклов в орграфе, но существует минимальный цикл, который не является объединением меньших циклов. Здесь я ищу только циклы с минимальным количеством ребер.

Answer 1

Запустите несколько поисков DFS, как в топологическом порядке: начните с произвольной вершины и продолжайте выполнение новых поисков DFS, если есть несколько неисследованных вершин.

В поиске, как только вы находите задний край, вы знаете, что (1) существует цикл (2) числа ребер в этом цикле. Если вам также нужно получить список ребер в цикле, сохраните массив для каждого «обнаруженного в настоящее время цикла» и заполните его, когда вы возвращаетесь в граф вызовов DFS. Если back-edge был узлом A-> B, когда вы достигнете заднего узла B, массив будет содержать все ребра в цикле.

Конечно, держите в пути «самый короткий цикл, найденный до сих пор», чтобы избежать кратковременных списков бухгалтерии для циклов, которые длиннее этого минимума.