Programme Java pour trouver le plus grand ensemble indépendant dans un graphique à l'aide de graphiques complémentaires

Il s'agit d'un programme Java exécuté en C qui utilise la méthode du complément de graphe pour trouver le plus grand ensemble autonome du graphe. Tout d’abord, le programme construit le complément du graphe d’entrée donné. Il met ensuite l'accent sur chaque sommet du graphe complémentaire et trouve récursivement l'ensemble libre maximum (MIS) en comptant ou en excluant le sommet actuel. Le programme garde une trace de l'estimation du plus grand ensemble gratuit trouvé jusqu'à présent et la renvoie comme résultat final. En exploitant des graphes complémentaires, nous sommes en mesure de transformer le problème de recherche du plus grand ensemble autonome en recherche de la plus grande clique dans le graphe original, obtenant ainsi une solution efficace.

Méthode à utiliser

• Méthode de craquage par force brute

Méthode violente

Une méthode par force brute pour trouver le plus grand ensemble autonome dans un graphe consiste à générer tous les sous-ensembles possibles de sommets dans le graphe et à vérifier si chaque sous-ensemble forme un ensemble libre. Dans un programme Java implémenté en C, le calcul est répété pour tous les sous-ensembles possibles et confirme que chaque sommet du sous-ensemble n'a aucun sommet adjacent dans le même sous-ensemble. En étudiant de manière exhaustive tous les sous-ensembles, le programme distingue l'ensemble libre le plus grand avec le plus grand nombre de sommets qui satisfont à cette condition. Néanmoins, en raison de sa complexité temporelle exponentielle, cette approche n’est pas adaptée aux graphes étendus, mais semble fondamentalement raisonnable pour les graphes plus petits.

Algorithme

• Initialisez la variable maxSetSize à 0, qui sert à stocker la valeur d'évaluation du plus grand ensemble autonome trouvé.

• Générez un sous-ensemble de tous les sommets possibles dans le graphique. Cela peut être fait en employant un processus de masquage de bits ou en mettant l'accent de manière récursive sur toutes les combinaisons de sommets possibles.

• Pour chaque sous-ensemble :

• Vérifiez si le sous-ensemble forme un ensemble autonome. Parcourez chaque sommet du sous-ensemble.

• Pour chaque sommet v du sous-ensemble, vérifiez s'il existe également un sommet adjacent u dans le sous-ensemble. Si un tel sommet adjacent est trouvé, la boucle est rompue puisque les sous-ensembles ne sont pas indépendants.

• Si aucun sommet voisin d'un sommet n'est trouvé dans le sous-ensemble, vérifiez maxSetSize si la métrique actuelle du sous-ensemble est supérieure à maxSetSize.

• La valeur de maxSetSize représentera l'estimation du plus grand ensemble indépendant trouvé.

• Facultativement, si vous avez besoin d'obtenir le véritable ensemble de sommets dans l'ensemble libre maximum, gardez une trace des sommets par rapport au sous-ensemble avec la taille extrême maximale.

• Renvoyer maxSetSize comme mesure du plus grand ensemble autonome. Si vous suivez un ensemble de sommets réel, le degré et l'ensemble de sommets correspondant sont renvoyés.

Exemple

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

Sortie

The size of the largest independent set is: 2

Conclusion

Cet article présente un programme Java implémenté en langage C, qui est utilisé pour trouver le plus grand ensemble libre du graphique. La méthode utilisée est : la méthode de la force brute. La méthode par force brute consiste à générer tous les sous-ensembles possibles de sommets et à vérifier si chaque sous-ensemble forme un ensemble libre. L'algorithme et sa mise en œuvre sont expliqués, ainsi que des exemples de code et des résultats de sortie. Ces méthodes proposent différentes stratégies pour résoudre le problème de la recherche du plus grand ensemble libre dans un graphique.

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!