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

Не надо!

Проверка отпечатка ключа хоста является неотъемлемой частью защиты вашего соединения. Слепое принятие любого ключа хоста сделает вас уязвимым для атак «человек посередине» .


Вместо этого используйте переключатель -hostkey , чтобы предоставить отпечаток ожидаемого / известного ключа хоста.

[string]$arguments = 'somehost -l somelogin -pw somepasswd ping -hostkey xx:xx:xx:xx:... -c 12 someOtherHost > /home/homeie/mePingTestResults.txt'

78
задан nes1983 7 October 2013 в 07:41
поделиться

4 ответа

Я попробовал бы к , сортируют график топологически , и если Вы не можете, тогда он имеет циклы.

88
ответ дан Community 24 November 2019 в 10:35
поделиться

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

можно проверить на циклы в связанном компоненте графика следующим образом. Найдите узел, который имеет только исходящие края. Если нет такого узла, то существует цикл. Запустите DFS в том узле. При пересечении каждого края проверьте, указывает ли край уже назад на узел на стеке. Это указывает на существование цикла. Если Вы не находите такого края, в том связанном компоненте нет никаких циклов.

, Поскольку Rutger Prins указывает, если Ваш график не соединен, необходимо повторить поиск на каждом связанном компоненте.

Как ссылка, решительно связанный алгоритм Тарьяна компонента тесно связан. Это также поможет Вам найти циклы, не просто сообщают, существуют ли они.

32
ответ дан Jay Conrod 24 November 2019 в 10:35
поделиться

Решение, данное ShuggyCoUk, является неполным, потому что это не могло бы проверить все узлы.


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Это имеет timecomplexity O (n+m) или O (n^2)

1
ответ дан 24 November 2019 в 10:35
поделиться

Лемма 22.11 из книги Введение в алгоритмы (второе издание) утверждает, что:

Ориентированный граф G является ацикличным тогда и только тогда, когда поиск в глубину G не дает никаких обратных краев

13
ответ дан 24 November 2019 в 10:35
поделиться
Другие вопросы по тегам:

Похожие вопросы: