NP问题：基于无向图的最小顶点覆盖的混合贪心算法（MGA）

#include
#include
#include
#include
#include
#include
#include#define MAX 100using namespace std;int n,m;
struct Edge
{int u,v;
};
struct Point
{int id;int degree,adj_degree;
} point[MAX];                   //点集
vector E;                 //边集
vector G[MAX];             //每个点的相邻点集（相当于一个二维变长数组）
int degree[MAX],adj_degree[MAX];//每个点的度数和邻接度数
bool del[MAX],vis[MAX];         //已删除的点集、已访问过的点集
int V_cnt,Vv_cnt,E_cnt;         //统计已经覆盖的顶点和边void init_edge()
{E.clear();for(int i=1; i<=n; i++) G[i].clear();
}
void add_edge(int u,int v)
{E.push_back((Edge) {u,v} );E.push_back((Edge) {v,u} );int _size=E.size();G[u].push_back(_size-2);G[v].push_back(_size-1);
}
bool cmp(Point a,Point b)
{return a.adj_degree>b.adj_degree;
}
void pretreat()                 //预处理：计算每个顶点的度数和邻接度数
{for(int i=1; i<=n; i++){point[i].degree=0;if(del[i]) continue;for(int j=0,_size=G[i].size(); j<_size; j++){Edge& e=E[G[i][j]];if(!del[e.v]) point[i].degree++;}//cout<<"第"<=Vv_cnt) break;        //该子图中的点全部被访问过了}//flag++;}//cout< s;FILE *fp;int u,v;char fname[100];cout<<"\n请输入顶点网络（文件名）：";gets(fname);while((fp=fopen(fname,"r"))==NULL) {cout<<"文件名输入错误，请重新输入！\n";break;}while(fscanf(fp,"%d %d\n",&u,&v)!=EOF){if(s.count(u)==0){s.insert(u);countN++;}if(s.count(v)==0){s.insert(v);countN++;}add_edge(u,v);countM++;}m=countM;n=countN;fclose(fp);
}
int main()
{/*cout<<"请输入图中顶点个数：";cin>>n;cout<<"请输入图中边数：";cin>>m;cout<<"请输入边(u,v)："<>u>>v;add_edge(u,v);}*///int maxNum=(int)ceil(log(m)/log(2));while(1){init_edge();fileInput();bool ans[n];                        //记录最小顶点覆盖集memset(ans,0,sizeof(ans));MinVC_MGA(ans);cout<<"最小控制顶点集为：";for(int i=1; i<=n; i++){if(ans[i]==true) cout<