Bina graf berdasarkan pasangan bucu yang disambungkan

Kandungan soalan

Saya perlu menyemak bilangan graf berasingan yang akan dibuat di mana "n baris mengandungi pasangan integer positif, di mana setiap pasangan mengenal pasti sambungan antara dua bucu dalam graf.". Katakan kita mempunyai 3 pasangan: [4 3], [1 4], [5 6]. Jawapannya ialah 2, kerana [4 3]&[1 4] akan digabungkan menjadi satu graf: [1 3 4], yang kedua ialah [5 6]. Jika kita menambah pasangan lain: [4 3], [1 4], [5 6], [4 6], jawapannya ialah 1 (hanya 1 graf: [1 3 4 5 6] disambungkan). p>

Saya berjaya menyelesaikan masalah ini menggunakan java, tetapi ia tidak cekap dan sangat perlahan untuk lebih daripada 10000 pasangan. Kod kelihatan lebih kurang seperti ini:

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);

        }
    }

Bagaimana untuk meningkatkan prestasi? Saya tidak meminta penyelesaian luar biasa, tetapi mungkin ada algoritma yang saya tidak sedar yang akan mempercepatkan keadaan dengan ketara?

Jawapan Betul

Untuk mendapatkan bilangan komponen yang disambungkan, anda boleh menggunakan set bercabang. Ini adalah pelaksanaan mudah dengan mengandaikan input ialah list tepi.

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;
}

Jika bilangan nod (n）已知，并且我们可以假设所有节点标签都是 1 和 n 之间的整数，我们可以通过使用数组而不是 map) dioptimumkan dan menjejaki bilangan komponen yang disambungkan semasa tepi ditambah.

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;
}

Atas ialah kandungan terperinci Bina graf berdasarkan pasangan bucu yang disambungkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!