什么是最有效的方法，以确定是否有向图被单独地连接？ [英] What is the most efficient way to determine if a directed graph is singly connected?

问题描述

我的工作分配，其中的一个问题问得出一个算法，以检查是否有向图G =（V，E）是单连通（有从u至多一个简单的路径，以v对于所有不同顶点U，V诉。

I am working on an assignment where one of the problems asks to derive an algorithm to check if a directed graph G=(V,E) is singly connected (there is at most one simple path from u to v for all distinct vertices u,v of V.

当然，你可以蛮力检查，这是我在做什么的权利，但我想知道如果有一个更有效的方法。任何人都可以点我在正确的方向？

Of course you can brute force check it, which is what I'm doing right now, but I want to know if there's a more efficient way. Could anyone point me in the right direction?

推荐答案

您是否尝试过 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因为没有重复。

Complexity O(v^2), o(v) dfs as no repetition.

这篇关于什么是最有效的方法，以确定是否有向图被单独地连接？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！