确定有向图是否是单边的 [英] Determining if a directed graph is unilateral

问题描述

您将如何找出有向图是否是单边的(对于任意一对顶点u，v，至少有一个顶点可以相互到达)? 我在想您可以运行DFS或BFS，看看是否可以到达每个顶点.如果不是，请计算转置并从相同的顶点执行相同的搜索算法.如果您已至少到达每个顶点，那么图是单边的吗?

How would you go about finding out if a directed graph is unilateral (for any pair of verticles u,v, at least one is reachable from the other)? I'm thinking that you could run DFS or BFS and see if you can reach every vertex. If not, compute the transpose and do the same search algorithm from the same vertex. If you have reached every vertex at least one, is the graph unilateral?

很显然，您可以通过分析邻接矩阵来在较大的运行时间中执行此操作，但理想情况下，我们希望在O(V + E)中运行

Obviously you could do this in large running times by just analyzing an adjacency matrix, but ideally we want to run in O(V+E)

推荐答案

我不完全确定这是否正确，但是我认为检查图是否连接"就足够了(请参阅下面的算法说明)以了解我的意思是连接".如果有向图中有多个相连的组件，那么它不是单边的.

I am not entirely sure whether this is correct, but I think that it should suffice to check if the digraph is "connected" (see description of the algorithm below to find out what I mean by connected). If there are multiple connected components in the digraph, then it is not unilateral.

验证尝试:

假设有向图具有多个连接的组件.为简单起见，让连接的组件数为2，将其称为组件C1和C2.从C1中选择任何顶点v，并从C2中选择任何顶点w.由于它们位于不同的连接组件中，因此从v到w或w到v没有路径，否则C1和C2将在同一组件中.

Suppose that the digraph has multiple connected components. For simplicity's sake, let the number of connected components be 2, and let's call the components C1 and C2. Select any vertex v from C1 and any vertex w from C2. Since they are in different connected components, there is no path from v to w or w to v, otherwise C1 and C2 will be in the same component.

对于另一种情况，假设连接了有向图.然后，对于有向图中的任何两个不同的顶点x和y，都存在从x到y或从y到x的路径，否则它们将不在同一组件中.我知道这里有点波浪，但是我并不擅长打样.

For the other case, suppose that a digraph is connected. Then for any 2 distinct vertices x and y in the digraph, there is either a path from x to y or from y to x, otherwise they will not be in the same component. I know it's a bit hand wavy here, but I'm not exactly good at proofs.

一种更简单的算法:

我认为修改后的深度优先搜索/宽度优先搜索应该可以.本质上，我们可以从 any 顶点开始搜索.我们将所有从第一个顶点可达的顶点标记为已访问.然后遍历所有顶点.对于任何未访问的顶点，我们进行BFS/DFS，并使用列表来跟踪已遍历的所有未访问的顶点.如果在BFS/DFS期间，我们没有从先前的BFS/DFS访问任何先前访问的顶点，那么我们可以立即得出结论，该有向图具有多个相连的分量，并且不是单边的.否则，我们会将在搜索过程中获得的列表中的所有顶点标记为已访问，然后继续.

I do think a modified Depth First Search / Breadth First Search should be able to do it. Essentially, we can start the search from any vertex. We mark all vertices reachable from that first vertex as visited. Then loop through all vertices. For any unvisited vertex, we conduct a BFS / DFS, and we use a list to keep track of all unvisited vertices that we have traversed. If during the BFS / DFS, we do not visit any previously visited vertex from a prior BFS / DFS, then we can conclude immediately that the digraph has multiple connected components and is not unilateral. Otherwise, we mark all vertices in the list we obtained during the search as visited, and we continue.

一旦遍历图中的所有顶点，所有BFS/DFS都到达了先前访问过的某个顶点，我们可以得出结论，该图是单边的.

Once we have gone through all vertices in the graph all the BFS / DFS hit some previously visited vertex, we can conclude that the graph is unilateral.

一些伪代码来说明这一点.我将使用深度优先搜索:

Some pseudocode to illustrate this. I shall make use of 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的强连接组件算法 ，然后确定有向图的强连接组件.您将需要稍微修改算法，以将强连接的组件压缩为超顶点.这并不难，只需在同一强连接的组件中为每个顶点分配一个整数标签即可.换句话说，同一强连接组件中的所有顶点都将替换为1个超顶点. Tarjan的SCC(严格连接组件)算法在O(V+E)时间内运行.

How do we then compute if a digraph is unilateral? You can first run Tarjan's Strongly Connected Components algorithm and determine the strongly connected components of the digraph. You will need to modify the algorithm slightly to compress the strongly connected components into supervertices. This is not difficult to do, just assign each vertex in the same strongly connected component an integer label. In other words, all the vertices in the same strongly connected component will be replaced by 1 supervertex. Tarjan's SCC (Strongly Connected Components) algorithm runs in O(V+E) time.

完成上述步骤后，二合图现在非循环(无循环).这使我们可以继续下一步.

After the step above, the digraph is now acyclic (no cycles). This allows us to move on to the next step.

此后，从上方对结果图执行拓扑排序.这应该给我们有向无环图的拓扑顺序.使用深度优先搜索实现，此步骤还可以在O(V+E)时间内运行.

After that, perform a topological sort on the resulting graph from above. This should give us a topological ordering of the directed acyclic graph. This step also runs in O(V+E) time using a depth first search implementation.

现在我们有了拓扑顺序，根据拓扑顺序执行广度优先搜索或深度优先搜索 Tarjan的SCC步骤后获得的>有向无环图.如果连接的组件数为1，则原始图是单边的(如果连接的组件数为0，则它​​也是单边的，但这是一个空图，因此是微不足道的).否则，存在多个组成部分，并且原始图形不是单边的.此步骤也将在O(V+E)时间运行.

Now that we have the topological ordering, perform either Breadth First Search or Depth First Search according to the topological ordering on the directed acyclic graph obtained after the Tarjan's SCC step. If the number of connected components is 1, then the original graph is unilateral (it is also unilateral if the number of connected components is 0, but that is an empty graph and so is trivial). Otherwise, there are multiple components, and the original graph is not unilateral. This step also runs in O(V+E) time.

因此，整个算法在O(V+E)时间内运行.

Therefore, the overall algorithm runs in O(V+E) time.

结论

我认为这应该是正确的，但是您可能想与其他人一起验证这种方法.如果您在理解我的方法或实现算法方面遇到任何困难，请发表评论.

I think this should be correct, but you might want to verify this approach with someone else. If you have any difficulty in understanding my approach or implementing the algorithms, do leave a comment.

希望有帮助！

这篇关于确定有向图是否是单边的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！