如果有向图是单向的（对于任何一对眩晕，u，v，至少有一个是可以从另一个中获得的），您将如何着手找出？
我想你可以运行DFS或BFS，看看是否可以到达每个顶点如果不是，则计算转置并从同一顶点执行相同的搜索算法。如果你已经到达每个顶点至少一个，那么这个图是单向的吗？
显然，你可以通过分析一个邻接矩阵在大的运行时间内完成这项工作，但理想情况下我们希望在o（v+e）中运行。
最佳答案
我不完全确定这是否正确，但我认为检查有向图是否“连通”就足够了（请参阅下面的算法说明，以了解我所说的连通）。如果有向图中存在多个连通分量，则它不是单向的。
验证尝试：
假设有向图有多个连通分量。为了简单起见，让连接组件的数量为2，并调用组件C1和C2。从v中选择任意顶点C1，从w中选择任意顶点C2由于它们位于不同的连接组件中，因此没有从v到w或w到v的路径，否则C1和C2将位于同一组件中。
对于另一种情况，假设有向图是连通的。然后，对于有向图中的任意两个不同的顶点x和y，要么有一条从x到y或从y到x的路径，否则它们将不在同一个分量中。我知道这里有点手摇，但我不太擅长校对。
编辑：更简单的算法：
我认为修改后的深度优先搜索/宽度优先搜索应该能够做到这一点。实际上，我们可以从任何顶点开始搜索。我们将从第一个顶点到达的所有顶点标记为已访问然后循环通过所有顶点对于任何未访问的顶点，我们执行一个BFS/DFS，并使用一个列表来跟踪所有已遍历的未访问顶点如果在BFS/DFS过程中，我们没有从先前的BFS/DFS访问任何先前访问过的顶点，那么我们可以立即断定有向图有多个连通分量，并且不是单向的否则，我们将搜索期间获得的列表中的所有顶点标记为已访问，然后继续。
一旦我们遍历了图中的所有顶点，所有的BFS/DFS都碰到了一些以前访问过的顶点，我们就可以得出结论：图是单向的。
一些伪代码来说明这一点。我将利用深度优先搜索：
// 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个超顶点替换。tarjan的s cc（强连接组件）算法在
O(V+E)时间内运行。在上面的步骤之后，有向图现在是无环的（没有循环）。这使我们可以进入下一步。
之后，对上面得到的图执行拓扑排序。这应该给出有向无环图的拓扑序。此步骤还使用深度优先搜索实现在
O(V+E)时间内运行。现在我们有了拓扑排序，根据Tarjan的SCC步骤后得到的有向无环图的拓扑排序，执行广度优先搜索或深度优先搜索如果连通分量的个数为1，则原始图是单向的（如果连通分量的个数为0，则也是单向的，但这是一个空图，因此是平凡的）否则，存在多个组件，并且原始图不是单向的此步骤也在
O(V+E)时间内运行。因此，整个算法在
O(V+E)时间内运行。结论
我认为这应该是正确的，但是你可能想和其他人一起验证这种方法如果您在理解我的方法或实现算法方面有任何困难，请留下评论。
希望能有帮助！
关于algorithm - 确定有向图是否是单边的，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20694742/