最大獨立集

獨立集

獨立集是指圖 G 中兩兩互不相鄰的頂點構成的集合。任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP 困難的，從而尋找圖的最大獨立集也是 N-P 困難的。但是，對於二部圖的情形，有多項式時間算法找出圖的最大獨立集。

最大獨立集問題

如果U定義了G的一個完全子圖，則它也定義了的一個空子圖，反之亦然。所以在G的完備子圖與的獨立集之間有對應關係。特別的，G的一個最大完備子圖定義了的一個最大獨立集。

最大完備子圖問題是指尋找圖G的一個最大完備子圖。類似地，最大獨立集問題是指尋找圖G的一個最大獨立集。這兩個問題都是NP-複雜問題。當用算法解決其中一個問題時，也就解決了另一個問題。例如，如果有一個求解最大完備子圖問題的算法，則也能解決最大獨立集問題，方法是首先計算所給圖的補圖，然後尋找補圖的最大完備子圖。

算法思想

定義一個圖，圖中每個頂點表示一個網組。若且唯若兩個頂點對應的網組交叉時，它們之間有一條邊。所以該圖的一個最大獨立集對應於非交叉網組的一個最大尺寸的子集。當網組有一個端點在路徑頂端，而另一個在底端時，非交叉網組的最大尺寸的子集能在多項式時間（實際上是O(n²)）內用動態規划算法得到。當一個網組的端點可能在平面中的任意地方時，不可能有在多項式時間內找到非交叉網組的最大尺寸子集的算法。

首先選擇一點為樹根，再按照深度優先遍歷得到遍歷序列，按照所得序列的反向序列的順序進行貪心，對於一個即不屬於支配集也不與支配集中的點相連的點來說，如果他的父節點不屬於最大獨立集，將其父節點加入到獨立集。

具體實現

採用鏈式前向星存儲整棵樹。整形數組newpos[i]表示深度優先遍歷序列的第i個點是哪個點，now表示當前深度優先遍歷序列已經有多少個點了。bool形數組visit[ ]用於深度優先遍歷的判重，整形pre[i]表示點i的父節點編號, bool型數組s[i]如果為true,表示第i個點被覆蓋， bool型數組set[i]如果為true,表示點i屬於要求的點的集合。

#include <bits/stdc++.h>using namespace std;const int maxn = 1000;int pre[maxn];//存儲父節點bool visit[maxn];//DFS標記數組int newpos[maxn];//遍歷序列int now;int n, m;int head[maxn];//鏈式前向星struct Node {int to; int next;};Node edge[maxn]; void DFS(int x) {   newpos[now ++] = x;//記錄遍歷序列   for(int k = head[x]; k != -1; k = edge[k].next) {       if(!visit[ edge[k].to ]) {           visit[ edge[k].to ] = true;           pre[edge[k].to] = x;//記錄父節點           DFS(edge[k].to);       }   }} int MVC() {   bool s[maxn] = {0};   bool set[maxn] = {0};   int ans = 0;   for(int i = n - 1; i >= 1; i--) {//逆序進行貪心,排除掉其根節點       int t = newpos[i];       if(!s[t] && !s[ pre[t] ]) {//如果當前節點和其父節點都不屬於頂點覆蓋集合           set[ pre[t] ] = true;//把其父節點加入到頂點覆蓋集合           ans ++; //集合內頂點個數加1           s[t] = true;//標記當前節點被覆蓋           s[ pre[t] ] = true;//標記其父節點被覆蓋       }           }   return ans;} int main() {   /* read Graph message*/ //建圖   memset(visit, false, sizeof(visit));//初始化   now = 0;   visit[1] = true;   pre[1] = 1;   DFS(1);//從第一個根節點開始尋找遍歷序列   MDS();   return 0;}

最大獨立集

基本介紹

獨立集