Я работаю над заданием, в котором одна из проблем требует вывести алгоритм для проверки односвязного направленного графа G = (V, E) (существует не более одного простого пути от u до v для всех различных вершины u, v из V.
Конечно, вы можете проверить, что это я делаю прямо сейчас, но я хочу знать, есть ли более эффективный способ. Может ли кто-нибудь указать мне в правильном направлении?
Вы пробовали 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 как повторение.
Есть лучший ответ на этот вопрос. вы можете сделать это в O (| V | ^ 2). и с большим усилием вы можете сделать это в линейном времени.
Сначала вы найдете сильно связанные компоненты G. в каждом сильном компоненте, вы ищете для поиска таких случаев: 1) если в этом компоненте есть переднее ребро, оно не является односвязным, 2) если в этом компоненте имеется перекрестье, оно не является односвязным, 3) если в дереве есть как минимум два обратных кромки, укорененных в вершине u, правильным предкам u, то он не является односвязным.
это можно сделать в O (E). (Я думаю, кроме случая 3. Я не мог реализовать его хорошо!).
Если ни один из вышеперечисленных случаев не произошел, вы должны проверить, есть ли перекрестный край или передний край в G ^ SCC (граф G с сильными компонентами, замененными на единичные узлы), так как у нас нет поддержки, это может выполняются повторением dfs на каждой вершине этого графа в O (| V | ^ 2).
Прочитайте этот. Это действительно хорошо объясняет.
Я не согласен с тем, что его сложность будет O (V ^ 2), так как In DFS мы не называем ее для каждой вершины, как и во введении к книге алгоритмов, синтаксисом является DFS (G). Мы называем только DFS для целого графика не для какой-либо одной вершины, в отличие от BFS. Итак, здесь, в этом случае, по мне, мы должны проверить его, вызвав DFS один раз. Если вновь посещенная вершина встречается снова, график не связан по-отдельности (определенно, мы должны называть его для каждого отсоединенного компонента, но он уже включен в код). Таким образом, сложность будет O (V + E). Поскольку здесь E = V, сложность должна быть O (V).
Я подумал об этом: 1) Запустите DFS из любой вершины, если все вершины покрыты в DFS без передних ребер (не может быть никакого креста, так как иначе не все вершины будут покрыты), то он может быть потенциальным кандидатом.
2) Если вершина (уровень j), которая находится в DFS, имеет задний край к уровню i, то никакая другая вершина не найдена после того, как она должна иметь задний край к любой вершине с уровнем меньше j, и каждая вершина будет много достижимый до корня (проверяется со второй DFS).
Это выполняется в линейном времени, если это правильно.
Взгляните на определение простого пути. Циклический граф может быть односвязным. DFS не будет работать для A->B, B->A, который однократно подключен.
В следующей статье для решения этой проблемы используется сильно связанная компонента.
Запустите DFS один раз из каждой вершины. График односвязен, если и только если нет передних краев и нет перекрестных ребер внутри компонент.
Сложность: O (V.E)