本文主要是介绍图论 —— 弦图 —— MCS 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【概述】
MCS 算法是最大势算法（Maximum Cardinality Search），其常用于弦图的判定、求弦图的最大团、最小着色、最大独立集、最小团覆盖等。
一个无向图的弦图当且仅当其有一个完美消除序列，MCS 算法能够在 O(n+m) 内求出一个完美消除序列的反序。
每次执行 MCS 算法按从 n 到 1 的顺序依次给点标号，标号为 i 的点出现在完美消除序列的第 i 个，设 label[i] 为第 i 个点与多少个已标号点相邻，每次选择 label[i] 最大的未标号点进行标号，从而求一个完美消除序列的反序。
【算法核心】
vector<int> V[N];
void MCS() {for(int i=1; i<=n; i++)V[0].push_back(i);int maxx=0;int now=0;for(int i=1; i<=n; i++) { //从前往后bool flag=false;while(!flag) {for(int j=V[maxx].size()-1; j>=0; j--) { //从后往前if(vis[V[maxx][j]])V[maxx].pop_back();else {flag=true;now=V[maxx][j];break;}}if(!flag)maxx--;}vis[now]=true;//逆序存放order[n-i+1]=now;id[now]=n-i+1;for(int j=head[now]; j!=-1; j=edge[j].next) {int to=edge[j].to;if(!vis[to]) {label[to]++;V[label[to]].push_back(to);maxx=max(maxx,label[to]);}}}
}【模版】
struct Edge {int to,next;Edge() {}Edge(int to,int next):to(to),next(next) {}
};
struct MCS{Edge edge[N<<1];int head[N],tot;int n,m;bool vis[N];int id[N];//编号int label[N];//与多少标号点相邻int order[N];//完美消除序列vector<int> V[N];void init(int n,int m) {this->n=n;this->m=m;for(int i=1; i<=n; i++)V[i].clear();memset(head,-1,sizeof(head));memset(order,0,sizeof(order));memset(label,0,sizeof(label));memset(vis,0,sizeof(vis));memset(id,0,sizeof(id));tot=0;}void addEdge(int x,int y) {edge[tot].to=y;edge[tot].next=head[x];head[x]=tot++;}void mcs() {for(int i=1; i<=n; i++)V[0].push_back(i);int maxx=0;int now=0;for(int i=1; i<=n; i++) { //从前往后bool flag=false;while(!flag) {for(int j=V[maxx].size()-1; j>=0; j--) { //从后往前if(vis[V[maxx][j]])V[maxx].pop_back();else {flag=true;now=V[maxx][j];break;}}if(!flag)maxx--;}vis[now]=true;//逆序存放order[n-i+1]=now;id[now]=n-i+1;for(int j=head[now]; j!=-1; j=edge[j].next) {int to=edge[j].to;if(!vis[to]) {label[to]++;V[label[to]].push_back(to);maxx=max(maxx,label[to]);}}}}int bucket[N];//桶int judge() { //判断是否是弦图memset(vis,0,sizeof(vis));memset(bucket,0,sizeof(bucket));for(int i=n; i>0; i--) {int cnt=0;int ret=1;for(int j=head[order[i]]; j!=-1; j=edge[j].next)if(id[edge[j].to]>i)vis[bucket[++cnt]=edge[j].to]=1;for(int j=head[bucket[1]]; j!=-1; j=edge[j].next) {int to=edge[j].to;if(to!=bucket[1]&&vis[to]) {if(vis[to]) {ret++;vis[to]++;}}}for(int j=1; j<=cnt; j++)vis[bucket[j]]=0;if(cnt&&ret!=cnt)return false;}return true;}int getMaximumClique() { //计算最大团、最小着色int res=0;for(int i=1; i<=n; i++)res=max(res,label[i]+1);return res;}int getMaximumIndependentSet() { //计算最大独立集、最小团覆盖memset(vis,0,sizeof(vis));int res=0;for(int i=1; i<=n; i++) {if(!vis[order[i]]) {res++;vis[order[i]]=true;for(int j=head[order[i]]; j!=-1; j=edge[j].next)vis[edge[j].to]=true;}}return res;}
}mcs;
int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) {mcs.init(n,m);for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);mcs.addEdge(x,y);mcs.addEdge(y,x);}mcs.mcs();if(!mcs.judge())//若不为弦图printf("No\n");else { //若为弦图printf("Yes\n");int res1=mcs.getMaximumClique();//最大团、最小着色int res2=mcs.getMaximumIndependentSet();//最大独立集、最小团覆盖printf("The maximum clique:%d\n",res1);printf("The maximum independent set:%d\n",res2);}}return 0;
}
这篇关于图论 —— 弦图 —— MCS 算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
