获取图形的组件 (SCC)

Question

我是算法新手。我对下图感到困惑。我正在寻找下图中的强连通分量。

GRAPH

如果我没记错的话，连接应该是：A > D > E > C > B > F

谁能确定一下？或者如果我错了请纠正我？

我该如何描述/绘制该解决方案？对此有什么想法吗？

提前致谢

Answer 1

通过 definition，强连通分量将图划分为子图，这样，在每个子图中，每个节点都可以从每个节点到达。我们可以简单地将该定义应用到您的图表中以查看

• B 本身就是一个分量，因为它没有传入边。
• G 本身就是一个组件，因为它没有出边。
• C 本身就是一个分量，因为它唯一的出边是到 G。
• A、D、E、F 是一个组件。每个节点都可以从每个节点到达，因为它们形成了一个循环。