有向图中有多少个组件？

Question

我有以下图表：

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

这样做所需的算法是什么？

Answer 1

你混淆了两个定义。

对于无向图，存在连通分量的概念，您可以通过对无向图执行 DFS 来找到它。

对于有向图，存在强连通分量的概念，可以使用多种算法，所有算法都比简单的 DFS 稍微复杂一些。

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

Answer 2

我知道这是一个旧线程，但添加我如何解决问题会很有帮助：

1 - 找到图中的强连通分量 (SCC)，对于每个 SCC，我们可以将其替换为代表该 SCC 的单个节点。

2 - 现在，通过查看新图中节点的度数，我们可以知道可以运行 DFS 并覆盖所有其他节点的最小节点数，因此我们可以从度数为零的节点开始DFS。