Определение, является ли направленный граф односторонним.

Question

Как бы вы узнали, является ли направленный граф односторонним (для любой пары вершин u, v, по крайней мере один из них может быть достигнут от другого)? Я думаю, что вы можете запустить DFS или BFS и посмотреть, можете ли вы достичь каждой вершины. Если нет, вычислите транспонирование и выполните тот же алгоритм поиска из одной и той же вершины. Если вы достигли каждой вершины хотя бы один, то граф односторонний?

Очевидно, что вы могли бы сделать это в большое время работы, просто анализируя матрицу смежности, но в идеале мы хотим работать в O (V + E)

Answer 1

Я не совсем уверен, правильно ли это, но я думаю, что достаточно проверить, является ли орграф «подключенным» (см. Описание алгоритма ниже, чтобы узнать, что я подразумеваю под подключением). Если в орграфе есть несколько связанных компонентов, то это не односторонний.

Proof попытка:

Предположим, что орграф имеет несколько компонент связности. Для простоты позвольте числу подключенных компонентов быть 2, и назовем компоненты C1 и C2. Выберите любую вершину v от C1 и любую вершину w от C2. Поскольку они находятся в разных компонентах связи, нет пути от v до w или w до v, в противном случае C1 и C2 будут в том же компоненте.

Для другого случая предположим, что орграф связан. Тогда для любых 2 различных вершин x и y на орграфе есть либо путь от x до y, либо от y до x, иначе они не будут в одном компоненте. Я знаю, что здесь немного волнистая рука, но я не очень хорошо разбираюсь в доказательствах.

EDIT: простой алгоритм:

Я думаю МОДИФИЦИРОВАННЫЙ глубиной первого поиска/поиск в ширину должен быть в состоянии сделать это. По существу, мы можем начать поиск с любой вершины. Мы отмечаем все вершины, достижимые из этой первой вершины, по мере посещения. Затем проведите все вершины. Для любой невидимой вершины мы проводим BFS/DFS, и мы используем список для отслеживания всех невидимых вершин, которые мы прошли. Если во время BFS/DFS мы не посещаем ранее посещаемую вершину из предыдущей BFS/DFS, тогда мы можем сразу сделать вывод, что орграф имеет несколько подключенных компонентов и не является односторонним. В противном случае мы помечаем все вершины в списке, который мы получили во время поиска, и мы продолжим.

Как только мы пройдем через все вершины на графике, все BFS/DFS удалят некоторые ранее посещенные вершины, мы можем заключить, что график является односторонним.

Некоторые псевдокоды, чтобы проиллюстрировать это.Я буду использовать Depth First Search:

// a boolean array to keep track if a given vertex is visited 
// initially this is set to false 
boolean[] visited 
// boolean array to keep track of visited vertices for 2nd dfs onwards 
boolean[] visited_two 

// used for first dfs 
dfs(vertex) { 
    visited[vertex] <- true 
    for each edge leading out of vertex { 
    dfs(next vertex) 
    } 
} 

// used for subsequent dfs 
dfs_two(vertex, list_for_storing_vertices) { 
    // we use the visited_two array here, because the 
    // visited array is used to store previously visited 
    // vertices 
    visited_two[vertex] <- true 
    list_for_storing_vertices.append(vertex) 
    // return value. we return true if we encounter 
    // a previously visited vertex. otherwise, return false 
    return_value <- false 
    for each edge leading out of vertex { 
    if visited[next vertex] 
     return_value <- true 
    else if !visited_two[next_vertex] 
     r = dfs_two(next vertex, list_for_storing_vertices) 
     return_value = return_value || r 
    } 
    return return_value 
} 

// overall algorithm 
// Returns true if the graph is unilateral. false otherwise 
bool digraph_unilateral(graph) { 
    // Just pick any vertex. we will pick vertex 0 
    set all entries in `visited` array to false 
    dfs(0) 
    // then loop through all vertices. if they haven't been visited, 
    // we perform a dfs 
    for each vertex in the digraph { 
    if !visited[vertex] { 
     // reset visited_two array 
     set all entries in `visited_two` array to false 
     visited_list <- [] 
     encountered_previously_visited <- dfs_two(vertex, visited_list) 
     if encountered_previously_visited { 
     // mark the vertices we encountered as visited 
     for each v in visited_list { 
      visited[v] <- true 
     } 
     } else { 
     // we did not encounter any previously visited vertex 
     // so all vertices we encounter on this search are in 
     // a distinct connected component 
     return false 
     } 
    } 
    } 
    return true 
} 

Оригинал, более сложный алгоритм:

Как мы тогда вычислить, если орграф является односторонним? Вы можете сначала запустить Tarjan's Strongly Connected Components algorithm и определить сильно связанные компоненты орграфа. Вам нужно будет немного модифицировать алгоритм, чтобы сжать сильно связанные компоненты в суперверсии. Это не сложно сделать, просто назначьте каждую вершину в том же сильно связанном компоненте целочисленной меткой. Другими словами, все вершины в одной сильно связанной компоненте будут заменены на 1 супервертекс. Тарханский SCC (сильно подключенные компоненты) алгоритм работает в O(V+E) времени.

После шага выше, орграф теперь ациклический (без циклов). Это позволяет перейти к следующему шагу.

После этого выполните точный топологический вид на полученном выше графике. Это должно дать нам топологическое упорядочение ориентированного ациклического графа. Этот шаг также выполняется в O(V+E) времени с использованием реализации первого поиска глубины.

Теперь, когда мы имеем топологический порядок, выполнять либо поиск в ширину или Глубина поиска в согласно топологического упорядочения на направленного ациклического графа, полученного после стадии SCC в Tarján в. Если число подключенных компонентов равно 1, то исходный граф является односторонним (он также является односторонним, если число подключенных компонентов равно 0, но это пустой граф и, следовательно, тривиально). В противном случае существует несколько компонентов, а исходный график не является односторонним. Этот шаг также работает в O(V+E) раз.

Следовательно, общий алгоритм работает в O(V+E) раз.

Заключение

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

Надеюсь, что это поможет!

Answer 2

Попробуйте these algorithms. Я учился в колледже Флойд-Варшалл, но его производительность не так хороша, как вам хочется. Johnsons's algorithm быстрее для разреженных графиков, но все же O (V * E), а не O (V + E).