基于连接的顶点对构建图

问题内容

我需要检查将创建多少个单独的图，其中“n 行包含正整数对，其中每对标识图中两个顶点之间的连接。”。 假设我们有 3 对：[4 3]、[1 4]、[5 6]。 答案是 2，因为 [4 3]&[1 4] 将合并为一个图：[1 3 4]，第二个是 [5 6]。 如果我们再添加一对：[4 3]、[1 4]、[5 6]、[4 6]，答案将为 1（只有 1 个图：[1 3 4 5 6] 连接）。 p>

我设法用 java 解决了这个问题，但效率不高，对于超过 10000 对以上的情况，速度非常慢。代码看起来或多或少是这样的：

Set<Pair> connectionsSet;
    HashSet<TreeSet<Integer>> createdConnections;
    
    public void createGraphs() {
        for (Pair pair : connectionsSet) {
            boolean foundLeft = false, foundRight = false;
            for (TreeSet<Integer> singleSet : createdConnections) {
                if (singleSet.contains(pair.getLeft())) foundLeft = true;
                if (singleSet.contains(pair.getRight())) foundRight = true;
            }
            if (!foundLeft && !foundRight)
                addNewGraph(pair);
            else if (foundLeft && !foundRight)
                addToExistingGraph(pair, Constants.LEFT);
            else if (!foundLeft && foundRight)
                addToExistingGraph(pair, Constants.RIGHT);
            else if (foundLeft && foundRight)
                mergeGraphs(pair);
        }
    }

    private void addNewGraph(Pair pair) {
        createdConnections.add(new TreeSet<>(pair.asList()));
    }

    private void addToExistingGraph(Pair pair, String side) {
        for (TreeSet<Integer> singleSet : createdConnections) {
            if (side.equals(Constants.LEFT) && singleSet.contains(pair.getLeft()))
                singleSet.add(pair.getRight());
            if (side.equals(Constants.RIGHT) && singleSet.contains(pair.getRight()))
                singleSet.add(pair.getLeft());
        }
    }

    private void mergeGraphs(Pair pair) {
        Optional<TreeSet<Integer>> leftSetOptional = getOptional(pair.getLeft());
        Optional<TreeSet<Integer>> rightSetOptional = getOptional(pair.getRight());

        if (leftSetOptional.isPresent() && rightSetOptional.isPresent()){
            TreeSet<Integer> leftSet = leftSetOptional.get();
            TreeSet<Integer> rightSet = rightSetOptional.get();

            rightSet.addAll(leftSet);

            createdConnections.removeIf(singleSet -> singleSet.contains(pair.getLeft()));
            createdConnections.removeIf(singleSet -> singleSet.contains(pair.getRight()));
            createdConnections.add(rightSet);

        }
    }

如何提高性能？我并不是要求一个现成的解决方案，但也许有一种我不知道的算法可以显着加快速度？

正确答案

要获取连接组件的数量，您可以使用不相交集。这是一个简单的实现，假设输入为边的 list。

map<integer, integer> parent;
int find(int x) {
    int p = parent.getordefault(x, x);
    if (p != x) p = find(p);
    parent.put(x, p);
    return p;
}
public int numconnectedcomponents(list<pair> edges) {
    parent = new hashmap<>();
    for (var e : edges) {
        int lpar = find(e.getleft()), rpar = find(e.getright());
        parent.put(lpar, rpar);
    }
    int comps = 0;
    for (var k : parent.keyset())
        if (find(k) == k) ++comps;
    return comps;
}

如果节点数（n）已知，并且我们可以假设所有节点标签都是 1 和 n 之间的整数，我们可以通过使用数组而不是 map 进行优化，并在添加边时跟踪连接组件的数量.

int[] parent;
int find(int x) {
    return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
public int numConnectedComponents(int nodes, List<Pair> edges) {
    parent = new int[nodes + 1];
    int comps = 0;
    for (var e : edges) {
        if (parent[e.getLeft()] == 0) {
            parent[e.getLeft()] = e.getLeft();
            ++comps;
        }
        if (parent[e.getRight()] == 0) {
            parent[e.getRight()] = e.getRight();
            ++comps;
        }
        int lPar = find(e.getLeft()), rPar = find(e.getRight());
        if (lPar != rPar) {
            parent[lPar] = rPar;
            --comps;
        }
    }
    return comps;
}

以上是基于连接的顶点对构建图的详细内容。更多信息请关注PHP中文网其他相关文章！