Java-Programm zum Ermitteln der maximalen unabhängigen Menge in einem Diagramm mithilfe komplementärer Diagramme

Dies ist ein in C ausgeführtes Java-Programm, das die Graphkomplementmethode verwendet, um die größte autonome Menge im Diagramm zu finden. Zunächst erstellt das Programm das Komplement des gegebenen Eingabegraphen. Anschließend wird jeder Scheitelpunkt im Komplementärgraphen hervorgehoben und die maximale freie Menge (MIS) rekursiv ermittelt, indem der aktuelle Scheitelpunkt gezählt oder ausgeschlossen wird. Das Programm verfolgt die Schätzung des größten bisher gefundenen freien Satzes und gibt ihn als Endergebnis zurück. Durch die Nutzung komplementärer Graphen sind wir in der Lage, das Problem der Suche nach der größten autonomen Menge in die Suche nach der größten Clique im Originalgraphen umzuwandeln und so eine effiziente Lösung zu erreichen.

Anwendungsmethode

• Brute-Force-Cracking-Methode

Gewalttätige Methode

Eine Brute-Force-Methode zum Finden der größten autonomen Menge in einem Diagramm besteht darin, alle möglichen Teilmengen von Eckpunkten im Diagramm zu generieren und zu prüfen, ob jede Teilmenge eine freie Menge bildet. In einem in C implementierten Java-Programm wird die Berechnung für alle möglichen Teilmengen wiederholt und bestätigt, dass jeder Scheitelpunkt in der Teilmenge keine benachbarten Scheitelpunkte in derselben Teilmenge hat. Durch die umfassende Untersuchung aller Teilmengen ermittelt das Programm die größte freie Menge mit der höchsten Anzahl an Eckpunkten, die diese Bedingung erfüllen. Allerdings ist dieser Ansatz aufgrund seiner exponentiellen Zeitkomplexität nicht für erweiterte Graphen geeignet, erscheint aber für kleinere Graphen grundsätzlich sinnvoll.

Algorithmus

• Initialisieren Sie die Variable maxSetSize auf 0, die zum Speichern des Bewertungswerts der größten gefundenen autonomen Menge verwendet wird.

• Erzeugen Sie eine Teilmenge aller möglichen Eckpunkte im Diagramm. Dies kann durch den Einsatz eines Bitmaskierungsprozesses oder durch rekursive Hervorhebung aller möglichen Scheitelpunktkombinationen erfolgen.

• Für jede Teilmenge:

• Überprüfen Sie, ob die Teilmenge eine autonome Menge bildet. Iterieren Sie über jeden Scheitelpunkt in der Teilmenge.

• Überprüfen Sie für jeden Scheitelpunkt v in der Teilmenge, ob es auch einen benachbarten Scheitelpunkt u in der Teilmenge gibt. Wenn ein solcher benachbarter Scheitelpunkt gefunden wird, wird die Schleife unterbrochen, da die Teilmengen nicht unabhängig sind.

• Wenn in der Teilmenge keine Nachbarscheitelpunkte eines Scheitelpunkts gefunden werden, überprüfen Sie maxSetSize, ob die aktuelle Teilmengenmetrik größer als maxSetSize ist.

• Der Wert von maxSetSize stellt die Schätzung der größten gefundenen unabhängigen Menge dar.

• Optional: Wenn Sie den wahren Satz von Scheitelpunkten im maximalen freien Satz erhalten müssen, behalten Sie den Überblick über die Scheitelpunkte im Vergleich zur Teilmenge mit der maximalen extremen Größe.

• MaxSetSize als Maß für die größte autonome Menge zurückgeben. Wenn einem tatsächlichen Scheitelpunktsatz gefolgt wird, werden sowohl der Grad als auch der entsprechende Scheitelpunktsatz zurückgegeben.

Beispiel

#include <iostream>
#include <vector>

using namespace std;

bool hasAdjacentVertices(int v, vector<int>& subset, vector<vector<int>>& graph) {
   // Check if vertex v has any adjacent vertices within the subset
   for (int u : subset) {
      if (graph[v][u] == 1)
      return true;
   }
   return false;
}

int findLargestIndependentSet(vector<vector<int>>& graph) {
   int numVertices = graph.size();
   int maxSetSize = 0;

   // Generate all possible subsets of vertices
   for (int i = 0; i < (1 << numVertices); i++) {
      vector<int> subset;
      // Construct the current subset based on the bitmask
      for (int j = 0; j < numVertices; j++) {
         if (i & (1 << j))
         subset.push_back(j);
      }

      bool isIndependent = true;
      // Check if the subset forms an independent set
      for (int v : subset) {
         if (hasAdjacentVertices(v, subset, graph)) {
            // If an adjacent vertex exists within the subset, it is not an independent set
            isIndependent = false;
            break;
         }
      }

      if (isIndependent && subset.size() > maxSetSize)
         maxSetSize = subset.size();
   }

   return maxSetSize;
}

int main() {
   // Example adjacency matrix for a graph with 4 vertices
   vector<vector<int>> graph = {
      {0, 1, 1, 1},
      {1, 0, 1, 0},
      {1, 1, 0, 1},
      {1, 0, 1, 0}
   };

   int largestIndependentSetSize = findLargestIndependentSet(graph);
   cout << "The size of the largest independent set is: " << largestIndependentSetSize << endl;

   return 0;
}

Ausgabe

The size of the largest independent set is: 2

Fazit

In diesem Artikel wird ein in der C-Sprache implementiertes Java-Programm vorgestellt, mit dem der größte freie Satz im Diagramm ermittelt wird. Die verwendete Methode ist: Brute-Force-Methode. Die Brute-Force-Methode besteht darin, alle möglichen Teilmengen von Scheitelpunkten zu generieren und zu prüfen, ob jede Teilmenge eine freie Menge bildet. Der Algorithmus und seine Implementierung werden zusammen mit Beispielcode und Ausgabeergebnissen erläutert. Diese Methoden bieten verschiedene Strategien zur Lösung des Problems, die größte freie Menge in einem Diagramm zu finden.

Das obige ist der detaillierte Inhalt vonJava-Programm zum Ermitteln der maximalen unabhängigen Menge in einem Diagramm mithilfe komplementärer Diagramme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!