Erstellen Sie einen Graphen basierend auf verbundenen Scheitelpunktpaaren

Inhalt der Frage

Ich muss überprüfen, wie viele separate Diagramme erstellt werden, wobei „n Zeilen Paare positiver Ganzzahlen enthalten, wobei jedes Paar eine Verbindung zwischen zwei Eckpunkten im Diagramm identifiziert.“ Angenommen, wir haben 3 Paare: [4 3], [1 4], [5 6]. Die Antwort ist 2, da [4 3]&[1 4] zu einem Diagramm zusammengeführt werden: [1 3 4], das zweite ist [5 6]. Wenn wir ein weiteres Paar hinzufügen: [4 3], [1 4], [5 6], [4 6], lautet die Antwort 1 (nur 1 Graph: [1 3 4 5 6] verbunden). p>

Ich konnte dieses Problem mit Java lösen, aber es war nicht effizient und bei mehr als 10.000 Paaren sehr langsam. Der Code sieht ungefähr so ​​aus:

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

        }
    }

Wie kann die Leistung verbessert werden? Ich bitte nicht um eine Lösung von der Stange, aber vielleicht gibt es einen mir unbekannten Algorithmus, der die Dinge erheblich beschleunigen würde?

Richtige Antwort

Um die Anzahl der verbundenen Komponenten zu ermitteln, können Sie disjunkte Mengen verwenden. Dies ist eine einfache Implementierung unter der Annahme, dass die Eingabe list aus Kanten besteht.

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

Wenn die Anzahl der Knoten (n）已知，并且我们可以假设所有节点标签都是 1 和 n 之间的整数，我们可以通过使用数组而不是 map) optimiert ist und die Anzahl der verbundenen Komponenten verfolgt wird, wenn Kanten hinzugefügt werden.

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

Das obige ist der detaillierte Inhalt vonErstellen Sie einen Graphen basierend auf verbundenen Scheitelpunktpaaren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!