我有一个图表,其中包含未知数量的断开连接的子图。什么是找到它们的好算法(或 Java 库)?
最佳答案
我认为您要查找的内容通常称为 Flood Fill .是否通过 BFS 或 DFS 遍历图形取决于您。
基本上,您获取一个未标记(AKA 未着色)节点并为其分配一个新标签。您将相同的标签分配给与该节点相邻的所有节点,依此类推,分配给从该节点可到达的所有节点。
当无法标记更多可到达节点时,您可以通过选择另一个未标记节点重新开始。请注意,这个新节点未标记这一事实意味着它无法从我们之前的节点访问,因此位于另一个断开连接的组件中。
当没有更多未标记的节点时,您必须使用的不同标签的数量就是图形的组件数。每个节点的标签告诉您哪个节点是哪个组件的一部分。
关于java - 在图中查找所有断开连接的子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1348783/