Construire un graphique basé sur des paires de sommets connectés

Contenu de la question

Je dois vérifier combien de graphiques distincts seront créés où "n lignes contiennent des paires d'entiers positifs, où chaque paire identifie une connexion entre deux sommets du graphique.". Supposons que nous ayons 3 paires : [4 3], [1 4], [5 6]. La réponse est 2, car [4 3]&[1 4] seront fusionnés en un seul graphique : [1 3 4], le second est [5 6]. Si on ajoute une autre paire : [4 3], [1 4], [5 6], [4 6], la réponse sera 1 (un seul graphe : [1 3 4 5 6] connecté). p>

J'ai réussi à résoudre ce problème en utilisant Java, mais ce n'était pas efficace et très lent pour plus de 10 000 paires. Le code ressemble plus ou moins à ceci :

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

        }
    }

Comment améliorer les performances ? Je ne demande pas de solution prête à l'emploi, mais peut-être existe-t-il un algorithme que je ne connais pas qui accélérerait considérablement les choses ?

Bonne réponse

Pour obtenir le nombre de composants connectés, vous pouvez utiliser des ensembles disjoints. Il s'agit d'une implémentation simple en supposant que l'entrée est list d'arêtes.

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

Si le nombre de nœuds (n）已知，并且我们可以假设所有节点标签都是 1 和 n 之间的整数，我们可以通过使用数组而不是 map) est optimisé et permet de garder une trace du nombre de composants connectés à mesure que des arêtes sont ajoutées.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!