algorithm - 在图中查找不相交的顶点集

Question

我想找到一种简单的方法来生成图形中不相交部分的集合。也就是说，在下面的Graph中，我想得到两组{A, B, C, D}和{E, F}。

Answer 1

您可以使用任何图形遍历算法(BFS 和 DFS 是最常见的)。

每当算法“卡住”(没有更多节点可遍历)时，您已完成找到一个组件，标记它，然后选择一个尚未遍历的随机顶点来找到下一个组件。