java - 计算不相交的有向图

Question

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

因此，对于Example，如果顶点 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 个不相交的有向图。

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

Answer 1

从树中所有节点的列表开始。考虑这些您未访问的节点。

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

1. 创建一个空集，即“节点集”，以表示存在于当前节点图中的节点。
2. 从当前节点开始执行搜索。对于您在搜索中遇到的每个节点，将其从未访问的节点列表中删除，然后：（1）如果该节点已存在于另一个节点集中，则合并当前节点集和另一个节点集并停止搜索该节点，或 (2) 如果该节点已存在于当前节点集中，则停止从该节点搜索，或 (3) 如果您从未见过该节点，则将其添加到当前节点集中。

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

Answer 2

似乎您不需要强连接，因此非常有效的不相交集森林算法可以完成这项工作。在联合阶段之后，您只需计算 parent = self 的节点

PS Sedgewick 关于它的演讲

Answer 3

public int countDisjointSubgraphs() {
    int len = matrix.length;
    int[] nodes = new int[len];
    for (int i = 0 ; i < len ; i++) nodes[i] = i;
    for (int i = 0 ; i < len ; i++) {
        for (int j = 0 ; j < len ; j++) {
            if (matrix[i][j] || matrix[j][i])
                for (int k = 0 ; k < len ; k++)
                    if (nodes[k] == nodes[i]) nodes[k] = j;
        }
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i : nodes)
        if (list.indexOf(i) < 0) list.add(i);
    return list.size();
}