java - 编写一个程序来标记无向图的连通分量

Question

“编写一个程序来标记无向图的连通分量。换句话说，第一个组件的所有顶点都被赋予第一个组件的标签，第二个分量的所有顶点都被赋予第二个秒。 11.8 项目 403组件的标签等。你的算法应该通过定义任何由边连接的两个顶点是同一等价的成员类(class)。一旦处理完所有边，给定等价项中的所有顶点类将被连接。使用 UNION/FIND 实现第 6.2 节实现等价类。”

/** General Tree class implementation for UNION/FIND */
class ParPtrTree {
    private Integer [] array; // Node array

    public ParPtrTree(int size) {
        array = new Integer[size]; // Create node array
        for (int i=0; i<size; i++)
            array[i] = null;
    }

    /** Determine if nodes are in different trees */
    public boolean differ(int a, int b) {
        Integer root1 = FIND(a); // Find root of node a
        Integer root2 = FIND(b); // Find root of node b
        return root1 != root2; // Compare roots
    }

    /** Merge two subtrees */
    public void UNION(int a, int b) {
        Integer root1 = FIND(a); // Find root of node a
        Integer root2 = FIND(b); // Find root of node b
        if (root1 != root2)
            array[root2] = root1; // Merge
    }

    /** @return The root of curr’s tree */
    public Integer FIND(Integer curr) {
        if (array[curr] == null)
            return curr; // At root
        while (array[curr] != null)
            curr = array[curr];
        return curr;
    }

我和几个 friend 一直在困惑如何解决这个问题，不清楚输入是如何表示的，我们想到用 Java 实现 Shaffer 的数据结构和算法分析中的通用图结构，这样做广度优先搜索将其组织为树并反转指针，以便它适合此数据结构，但我不确定所有这些随机工作是否真的适用于我们试图完成的任务。

以前有人遇到过/做过这个问题吗？我们的教授没有触及这个问题本身，只是将其列在他的作业中。

Answer 1

嗯，看起来 ParPtrTree 实现了等价关系，尽管我无法弄清楚 Par 和 Ptr 代表什么。 UNION(a,b) 将等价 a === b 添加到关系中，从而添加 a 和 b 已经等价于，现在都变得等价于彼此。

无需给您太多细节:我认为作业只是建议:对于图中的每个节点N，找到所有节点N_i 存在从 N 到 N_i 的边，并调用 UNION(N, N_i)。完成后，等价关系中的等价类对应于图的连通分量。我认为您需要弄清楚如何从 ParPtrTree 中获取这些类，但请考虑使用 HashSet 来跟踪您已经完成的图形节点与 的东西。最好您可以向 ParPtrTree 添加一个方法来获取一些信息，因为该方法将能够访问 array，但我不知道您是否'重新允许这样做。

此外，正如我在评论中提到的，在 Integer 对象上使用 != 不起作用，因为它比较引用而不是值。但是，您不能盲目地将其更改为使用equals，因为引用可能为空。要查看两个 Integer 对象是否相等，您需要类似

a == b || (a != null && a.equals(b))

要测试它们是否不同，请对整个事物使用 !。