Program Java untuk mencari set bebas maksimum dalam graf menggunakan graf pelengkap

Ini ialah program Java yang dilaksanakan dalam C yang menggunakan kaedah pelengkap graf untuk mencari set autonomi terbesar dalam graf. Pertama, program membina pelengkap graf input yang diberikan. Ia kemudiannya menekankan setiap bucu dalam graf pelengkap dan secara rekursif mencari set bebas maksimum (MIS) dengan mengira atau mengecualikan bucu semasa. Program ini menjejaki anggaran set percuma terbesar yang ditemui setakat ini dan mengembalikannya sebagai hasil akhir. Dengan memanfaatkan graf pelengkap, kami dapat mengubah masalah mencari set autonomi terbesar kepada mencari klik terbesar dalam graf asal, sekali gus mencapai penyelesaian yang cekap.

Kaedah penggunaan

• Kaedah brute force cracking

Kaedah ganas

Kaedah brute-force untuk mencari set autonomi terbesar dalam graf melibatkan penjanaan semua subset bucu yang mungkin dalam graf dan menyemak sama ada setiap subset membentuk set bebas. Dalam program Java yang dilaksanakan dalam C, pengiraan diulang untuk semua subset yang mungkin dan mengesahkan bahawa setiap bucu dalam subset tidak mempunyai bucu bersebelahan dalam subset yang sama. Dengan menyiasat semua subset secara menyeluruh, program ini membezakan set percuma terbesar dengan bilangan bucu tertinggi yang memenuhi syarat ini. Namun, disebabkan kerumitan masa eksponennya, pendekatan ini tidak sesuai untuk graf lanjutan, tetapi nampaknya pada asasnya munasabah untuk graf yang lebih kecil.

Algoritma

• Mulakan pembolehubah maxSetSize kepada 0, yang digunakan untuk menyimpan nilai penilaian set autonomi terbesar yang ditemui.

• Hasilkan subset semua bucu yang mungkin dalam graf. Ini boleh dilakukan dengan menggunakan proses penutupan bit atau dengan menekankan secara rekursif semua gabungan puncak yang mungkin.

• Untuk setiap subset:

• Semak sama ada subset membentuk set autonomi. Ulangi setiap bucu dalam subset.

• Untuk setiap bucu v dalam subset, semak sama ada terdapat bucu u bersebelahan juga dalam subset. Jika bucu bersebelahan seperti itu ditemui, gelung dipecahkan kerana subset tidak bebas.

• Jika tiada bucu jiran mana-mana bucu ditemui dalam subset, semak maxSetSize jika metrik subset semasa lebih besar daripada maxSetSize.

• Nilai maxSetSize akan mewakili anggaran set bebas terbesar yang ditemui.

• Secara pilihan, jika anda perlu mendapatkan set bucu sebenar dalam set bebas maksimum, jejaki bucu berbanding subset dengan saiz ekstrem maksimum.

• Kembalikan maxSetSize sebagai ukuran set autonomi terbesar. Jika mengikut set bucu sebenar, kedua-dua darjah dan set bucu sepadan dikembalikan.

Contoh

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

Output

The size of the largest independent set is: 2

Kesimpulan

Artikel ini memperkenalkan program Java yang dilaksanakan dalam bahasa C, yang digunakan untuk mencari set percuma terbesar dalam carta Kaedah yang digunakan ialah: kaedah brute force. Kaedah brute force terdiri daripada menjana semua subset bucu yang mungkin dan menyemak sama ada setiap subset membentuk set bebas. Algoritma dan pelaksanaannya dijelaskan, bersama dengan contoh kod dan hasil output. Kaedah ini menyediakan strategi yang berbeza untuk menyelesaikan masalah mencari set bebas terbesar dalam graf.

Atas ialah kandungan terperinci Program Java untuk mencari set bebas maksimum dalam graf menggunakan graf pelengkap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!