graph-theory - 我们如何遍历连通有向图的所有节点（因为某些根可能无法访问）？

Question

我想在有向图中找到连接组件的数量，但是如果我们尝试使用从 1 到 n 遍历节点并且每个节点到达其所有连接节点的通用方法，如果我们找到任何未到达的节点，那么我们将把该节点作为另一个组件。

.在这个例子中，至少4个或7个中的一个不能被遍历为相同的（并且只有从那里开始时才会被访问）。因此，请向我展示可以将其视为图形的相同组件的算法。

标签： graph-theorydirected-graphconnected-components

Answer 1

节点 4 和 7 彼此不可达，因为它们的入度为零。也就是说，没有指向它们的有向边。

如果您出于某种原因想将它们视为“连接”，因为它们有边将它们“连接”到图形的其余部分，即使边以“错误”的方式定向，那么您必须修改图形以替换所有有向边和无向边，然后运行“通用方法”。