Как найти кратчайший направленный цикл в ориентированном графе? - PullRequest
Новая
       36

Как найти кратчайший направленный цикл в ориентированном графе?

0 голосов
/ 24 июня 2018

С https://algs4.cs.princeton.edu/42digraph/

  1. Самый короткий направленный цикл. Учитывая заданный орграф, разработайте алгоритм для поиска направленного цикла с минимальным числом ребер (или сообщите, что график ациклический). Время работы вашего алгоритма должно быть пропорционально E V в худшем случае.

Решение найдено здесь: https://algs4.cs.princeton.edu/42digraph/ShortestDirectedCycle.java.html

public ShortestDirectedCycle(Digraph G) {
    Digraph R = G.reverse();
    length = G.V() + 1;
    for (int v = 0; v < G.V(); v++) {
        BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
        for (int w : G.adj(v)) {
            if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
                length = bfs.distTo(w) + 1;
                cycle = new Stack<Integer>();
                for (int x : bfs.pathTo(w))
                    cycle.push(x);
                cycle.push(v);
            }
        }
    }
}

Решение имеет смысл для меня, за исключением первой строки G.reverse(). Зачем? Это как-то связано с топологической сортировкой?

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

Как найти кратчайший цикл в ориентированном взвешенном графике?

Найти кратчайший цикл на графике

Нахождение кратчайших циклов в ориентированном или неориентированном графе (это для неориентированного графа) * ​​1030 *

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

1 Ответ

0 голосов
/ 24 июня 2018

G.reverse() - орграф, аналогичный G , за исключением , в котором каждый край перевернут; так, например, если G имеет ребро от v до w, то G.reverse() имеет ребро от w до v.

Поскольку bfs взято из G.reverse() и v, bfs.hasPathTo(w) означает "есть ли у G путь от w до v ", а bfs.distTo(w) означает" длина пути G от w до v ". (Если бы G было взято из *1029* вместо G.reverse(), он обнаружил бы пути, идущие в другую сторону.)

Таким образом, алгоритм поиска циклов, который он использует: для каждого ребра (v, w) в G, проверьте, есть ли у G путь от w до v.

Топологическая сортировка не задействована.

...