使用补图找到图中最大独立集的Java程序

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

The size of the largest independent set is: 2