Что состоит в том, чтобы определить самый эффективный путь, является ли ориентированный граф односвязным?
Я работаю над присвоением, где одна из проблем просит получать алгоритм, чтобы проверить, является ли ориентированный граф G = (V, E) односвязным (существует самое большее один простой контур от u до v для всех отличных вершин u, v V.
Конечно, Вы можете грубая сила проверять его, который является тем, что я делаю прямо сейчас, но я хочу знать, существует ли более эффективный путь. Кто-либо мог указать на меня в правильном направлении?
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 как отсутствие повторения.
Есть лучший ответ на этот вопрос. вы можете сделать это за O(|V|^2). и с большими усилиями вы можете сделать это за линейное время.
Сначала вы находите сильно связные компоненты G. В каждой сильной компоненте вы ищете такие случаи: 1) если в этой компоненте есть прямое ребро, то она не является односвязной, 2) если в этой компоненте есть поперечное ребро, то она не является односвязной, 3) если в дереве с корнем в вершине u есть хотя бы два обратных ребра к соответствующим предкам u, то оно не является односвязным.
это можно сделать за O(E). (Я думаю, кроме случая 3. Я не смог реализовать это хорошо!!!).
Если ни один из вышеперечисленных случаев не произошел, нужно проверить, есть ли перекрестное или прямое ребро на G^SCC (граф G, в котором сильные компоненты заменены одиночными вершинами), так как у нас нет бэкграундов, это можно сделать, повторив dfs на каждой вершине этого графа за O(|V|^2).