graph - 有向图中有多少个组件？

Question

我有以下图表:


最佳解决方案是从顶点 (3) 开始 dfs，然后我将得到一个分量，但是当我们从顶点 (1) 开始 dfs 时，则 (3) 我将得到两个分量。
问题是:
我想知道这个图中有多少个组件？或者以其他方式，覆盖所有图形所需的最少 dfs 数量是多少？
这样做所需的算法是什么？

Answer 1

你混淆了两个定义。

对于无向图，有 connected components 的概念，您可以通过在无向图上执行 DFS 来找到它。

对于有向图，有 strongly connected components 的概念，有多种算法可用，都比简单的 DFS 稍微复杂一些。

你应该做什么取决于你需要这两个概念中的哪一个。当被视为无向图时，你的图有一个连通分量，当被视为有向图时有两个强连通分量。