Как наиболее эффективный способ определить, подключен ли направленный график?

Question

Я работаю над заданием, в котором одна из проблем просит получить алгоритм, чтобы проверить, является ли направленное график g = (v, e) по отдельности (существует не более одного простого пути от u до v для всех отдельных вершин u, V из V.

Конечно, вы можете грубо проверить это, что я сейчас делаю, но я хочу знать, есть ли более эффективный способ. Может ли кто -нибудь указать мне в правильном направлении?

Answer 1

Ты пытался DFS.

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

Сложность O (V^2), O (V) DFS как не повторение.

Answer 2

На этот вопрос есть лучший ответ. Вы можете сделать это в O (| V |^2). И с большим усилием вы можете сделать это в линейное время.

Сначала вы находите тесно связанные компоненты G. В каждом сильном компоненте вы ищете, чтобы найти эти случаи: 1) Если в этом компоненте есть прямое край , он не связан с по отдельности, 3) Если в вершине U есть как минимум два заднего края, прикованного к вершине U, для правильных предков U, то это не связано с по отдельности.

Это можно сделать в O (E). (Я думаю, за исключением случая 3. Я не мог бы реализовать это хорошо !!).

Если ни один из приведенных выше случаев не произошел, вы должны проверить, есть ли поперечный край или прямое крайний край на G^SCC (график G, с сильными компонентами, замененными отдельными узлами), поскольку у нас нет приподнятых. Повторяя DFS на каждой вершине этого графика в O (| V |^2).

Answer 3

Читать Вот этот. Анкет Это действительно хорошо объясняет.

Answer 4

Я не согласен с тем, что его сложность будет o (v^2), как и в DFS, мы не называем его для каждой вершины, как и во введении в книгу алгоритма, синтаксис - это DFS (G). Мы называем DFS только для всего графика, а не для какой -либо одной вершины в отличие от BFS. Так что здесь, в этом случае, по моему мнению, мы должны проверить его, позвонив в DFS один раз. ) Таким образом, сложность будет O (V+E). Как здесь e = V, поэтому сложность должна быть O (v).

Answer 5

Я подумал об этом: 1) Запустите DFS из любой вершины, если все вершины покрыты в DFS без каких -либо прямого края (не может быть ни одного креста, так как еще не все вершины будут покрыты), то это может быть потенциальным кандидатом.

2) Если вершина (уровень j), которая находится в DFS, имеет задний край до уровня I, то друга Корень (проверяется со вторым DFS).

Это делает это в линейное время, если это правильно.

Answer 6

Взгляните на определение простого пути. Циклический график может быть по отдельности. DFS не будет работать для A->B, B->A, который по отдельности связан.

В следующей статье используется сильно подключенный компонент для решения этого.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 7

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

Сложность: o (ve)