java - 计算不相交的有向图

我有一个名为 boolean[][] 的 matrix 二维数组，它编码一个有向图，如果 matrix[i][j] == true ，则顶点 j 连接到顶点 i (反之不一定为真)。
我正在尝试创建一个 Java 方法来确定我有多少不相交的有向图。

所以对于 示例 ，如果顶点 0 连接到顶点 1，顶点 2 连接到顶点 3(<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array) ，我会有 2 个不相交的有向图。

如果没有连接，不相交的有向图的数量将等于顶点的数量。

最佳答案

从树中所有节点的列表开始。将这些视为您未访问的节点。

然后重复以下过程，直到您的未访问节点列表消失。

创建一个空集，即“节点集”，以表示当前节点图中的节点。

从当前节点开始执行搜索。对于您在搜索中遇到的每个节点，将其从未访问的节点列表中删除，然后:(1)如果该节点已存在于另一个节点集中，则合并当前节点集和其他节点集并停止搜索该节点，或 (2) 如果该节点已存在于当前节点集中，则停止从该节点搜索，或 (3) 如果您从未见过该节点，请将其添加到当前节点集中。

完成此过程后，您的节点集对应于每个不相交图中唯一存在的节点，因此节点集的数量就是您寻求的值。

关于java - 计算不相交的有向图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10694986/