Fragen Sie die Anzahl der verbundenen Komponenten ab, nachdem Sie einen Scheitelpunkt aus dem Baum entfernt haben

Mit der folgenden Abfrage können die nach dem Entfernen der Baumscheitelpunkte verbleibenden verbundenen Komponenten ermittelt werden: Betrachten Sie zunächst die Baumstruktur. Anschließend wird jede verbundene Komponente untersucht, indem sie sich mithilfe eines Breiten- oder Tiefensuchalgorithmus durch den Baum bewegt. Sobald die erforderlichen Eckpunkte entfernt sind, wird dieselbe Traversierungsmethode verwendet, um die Anzahl der verbundenen Komponenten zu bestimmen. Das Ergebnis wird anhand der Veränderung der Zählungen vor und nach dem Ausschluss ermittelt. Diese Methode überwacht effektiv Verbindungsänderungen und hilft bei der Berechnung von Aktualisierungen verbundener Komponenten im Baum.

Methode zur Verwendung

• Depth First Search (DFS)-Methode

• Und überprüfen Sie die Methode

Depth First Search (DFS)-Methode

Bei der DFS-Methode führen wir zunächst eine DFS-Durchquerung von einem beliebigen ausgewählten Knoten im ursprünglichen Baum aus, um die verbundenen Komponenten zu zählen, nachdem wir die Eckpunkte aus dem Baum entfernt haben. Während dieser Durchquerung durchlaufen wir jeden verbundenen Knoten, markieren jeden Knoten als besucht und verfolgen, wie oft DFS verwendet wurde. Nach dem Löschen eines bestimmten Scheitelpunkts führen wir eine neue DFS-Durchquerung durch und stellen so sicher, dass gelöschte Scheitelpunkte während der Erkundungsphase übersprungen werden. Wir können die Anzahl der verbundenen Komponenten im aktualisierten Baum ermitteln, indem wir die Anzahl der DFS-Aufrufe vor und nach dem Löschen vergleichen. Mit dieser Methode kann die Anzahl der verbundenen Elemente effizient gezählt und gleichzeitig Änderungen in der Baumstruktur berücksichtigt werden.

Algorithmus

• Wählen Sie einen beliebigen Scheitelpunkt im ursprünglichen Baum als Ausgangspunkt für die DFS-Durchquerung.

• Setzen Sie die Variable „count“, um mit dem Zählen verbundener Komponenten zu beginnen. Setzen Sie es zunächst auf 0.

• Verwenden Sie DFS vom ausgewählten Startscheitelpunkt aus, um den Baum zu durchqueren.

• Markieren Sie jeden während der DFS-Durchquerung besuchten Scheitelpunkt und erhöhen Sie die „Anzahl“ um 1 für jeden neuen DFS-Aufruf (d. h. für jede gefundene verbundene Komponente).

• Nachdem die DFS-Durchquerung abgeschlossen ist, wird die Anzahl der verbundenen Elemente im ursprünglichen Baum durch „count“ dargestellt.

• Entfernen Sie den angegebenen Scheitelpunkt aus dem Baum.

• Wiederholen Sie die DFS-Durchquerung vom selben Startscheitelpunkt aus und achten Sie darauf, gelöschte Scheitelpunkte nicht zu erkunden.

• Aktualisieren Sie beim Ausführen von DFS die Variable „count“ auf ähnliche Weise wie zuvor.

• Die Anzahl der zugehörigen Komponenten im aktualisierten Baum wird durch Subtrahieren der „Anzahl“ nach der Evakuierung von der anfänglichen „Anzahl“ ermittelt.

Beispiel

#include <iostream>
#include <vector>

void dfs(const std::vector<std::vector<int>>& tree, int v, 
std::vector<bool>& visited, int& count) {
   visited[v] = true;
   count++;
   for (int u : tree[v]) {
      if (!visited[u]) {
         dfs(tree, u, visited, count);
      }
   }
}

int countConnectedComponents(const std::vector<std::vector<int>>& tree, int startVertex) {
   int n = tree.size();
   std::vector<bool> visited(n, false);
   int count = 0;

   dfs(tree, startVertex, visited, count);
   return count;
}

int main() {
   std::vector<std::vector<int>> tree = {
      {1, 2},
      {0, 3},
      {0, 4},
      {1},
      {2}
   };

   int startVertex = 0;
   std::cout << countConnectedComponents(tree, startVertex) << std::endl;
   return 0;
}

Ausgabe

5

Und überprüfen Sie die Methode

Wir initialisieren zunächst jeden Scheitelpunkt als separate Komponente in der Union-Find-Methode, damit wir die verbundenen Komponenten zählen können, nachdem wir den Scheitelpunkt aus dem Baum entfernt haben. Um den Überblick über Teile und Verbindungen im ursprünglichen Baum zu behalten, suchen wir nach Datenstrukturen. Wir aktualisieren und fragen die Datenstruktur ab, um die Änderung der Baumkonnektivität nach dem Löschen des angegebenen Scheitelpunkts widerzuspiegeln. Zählen und überprüfen Sie dann die Anzahl der verschiedenen Sätze in der Datenstruktur. Die resultierende Anzahl stellt die Konnektivität der aktualisierten Komponenten des Baums dar. Nach dem Entfernen von Scheitelpunkten kann die Suchmethode verbundene Komponenten effizient berechnen und Strukturänderungen im Baum effektiv verarbeiten.

Algorithmus

• Erstellen Sie ein Array oder eine Datenstruktur von Grund auf, um jeden Scheitelpunkt als einen anderen Teil des Baums darzustellen. Zunächst ist jeder Scheitelpunkt sein eigener übergeordneter Scheitelpunkt.

• Verwenden Sie die UND-Suchoperation im Vorverarbeitungsschritt, um die Anzahl verbundener Komponenten des ursprünglichen Baums zu bestimmen.

• Verwenden Sie die Union-Datenstruktur, um die Teile des Baums zu kombinieren, die die Eckpunkte u und v für jede Kante (u, v) enthalten. In diesem Schritt wird die anfängliche Konnektivität des Baums hergestellt.

• Entfernen Sie den angegebenen Scheitelpunkt aus dem Baum.

• Wenden Sie die Union-Lookup-Operation des Vorverarbeitungsschritts auf den geänderten Baum an.

• Berechnen und überprüfen Sie nach dem Löschen die Anzahl der verschiedenen Elternvertreter in der Datenstruktur.

• Die Ergebnisanzahl stellt die Konnektivität der Baumaktualisierungskomponente dar.

Beispiel

#include <iostream>
#include <vector>

class UnionFind {
public:
   UnionFind(int n) {
      parent.resize(n);
      for (int i = 0; i < n; ++i) {
         parent[i] = i;
      }
   }

   int find(int u) {
      if (parent[u] != u) {
         parent[u] = find(parent[u]);
      }
      return parent[u];
   }

   void unite(int u, int v) {
      int rootU = find(u);
      int rootV = find(v);
      if (rootU != rootV) {
         parent[rootU] = rootV;
      }
   }

   int countDistinctParentRepresentatives() {
      int n = parent.size();
      std::vector<bool> distinct(n, false);
      for (int i = 0; i < n; ++i) {
         distinct[find(i)] = true;
      }
      int count = 0;
      for (bool isDistinct : distinct) {
         if (isDistinct) {
            count++;
         }
      }
      return count;
   }

private:
   std::vector<int> parent;
};

int main() {
   int n = 5;
   UnionFind uf(n);

   uf.unite(0, 1);
   uf.unite(0, 2);
   uf.unite(2, 3);
   uf.unite(2, 4);

   std::cout << uf.countDistinctParentRepresentatives() << 
std::endl;
   return 0;
}

Ausgabe

1

Fazit

Zusammenfassend lässt sich sagen, dass die vorgestellte Methode die Anzahl der verbundenen Teile im Baum nach dem Entfernen eines bestimmten Scheitelpunkts effizient zählen kann. Konnektivitätsänderungen in Baumstrukturen können mithilfe von DFS-Methoden (Depth First Search) und Union Search-Methoden effizient verarbeitet werden. Die DFS-Methode startet die Durchquerung am ausgewählten Scheitelpunkt, markiert jeden besuchten Knoten und zählt die verbundenen Komponenten. Die aktualisierte Anzahl wird durch Vergleichen der Anzahl vor und nach dem Durchlauf nach dem Löschen des Scheitelpunkts ermittelt und ein neuer Durchlauf ohne Einbeziehung des gelöschten Knotens durchgeführt.

Die anfängliche Anzahl verbundener Komponenten wird mithilfe einer Vereinigungsoperation über die Union-Find-Methode ermittelt, die jeden Scheitelpunkt als separate Komponente initialisiert. Wenden Sie nach dem Löschen der Scheitelpunkte dieselbe Vereinigungsoperation an und zählen Sie die verschiedenen übergeordneten Vertreter, um eine aktualisierte Anzahl zu erhalten.

Beide Methoden können nützliche Einblicke in die Konnektivität des Baums nach dem Entfernen von Scheitelpunkten liefern und eignen sich für eine Vielzahl von Szenarien.

Das obige ist der detaillierte Inhalt vonFragen Sie die Anzahl der verbundenen Komponenten ab, nachdem Sie einen Scheitelpunkt aus dem Baum entfernt haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!