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

Question

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

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

Answer 1

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

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

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

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

Answer 2

Вы пробовали 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 3

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

Сложность: O (V.E)