基於連接的頂點對構建圖

問題內容

我需要檢查將創建多少個單獨的圖，其中「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中文網其他相關文章！