C ++程序实现启发式以查找图形的顶点覆盖

  • Z时代
  • 2024-01-10
  • 分类：综合

图的顶点覆盖是要找到一组顶点V，这样对于图中M到N的每个边，在V中都存在M或N（或两者）。在此程序中，我们实现了一种启发式算法来查找图的顶点覆盖。

算法

Begin
   1) Initialize a set S as empty.
   2) Take an edge E of the connecting graph Say M and N.
   3) Add both vertex to the set S.
   4) Discard all edges in the graph with endpoints at M or N.
   5) If some edge is still left in the graph Go to step 2,
   6) Print the final set S is a vertex cover of the graph.
End

示例

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool v[11110];
int i,j;
vector<int> sol_vertex(int n,int e) {
   vector<int> S;
   for(i=0;i<n;i++) {
      if(!v[i]) {
         for(j=0;j<(int)g[i].size();j++) {
            if(!v[g[i][j]]) {
               v[i]=true;
               v[g[i][j]]=true;
               break;
            }
         }
      }
   }
   for(i=0;i<n;i++)
      if(v[i])
   S.push_back(i);
   return S;
}
int main() {
   int n,e,a,b;
   cout<<"输入顶点数：";
   cin>>n;
   cout<<"输入边数：";
   cin>>e;
   g.resize(n);
   memset(v,0,sizeof(v));
   for(i=0;i<e;i++) {
      cout<<"Enter the end-points of edge "<<i+1<<" : ";
      cin>>a>>b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   vector<int> S = sol_vertex(n,e);
   cout<<"The required vertex cover is as follows:\n";
   for(i=0;i<(int)S.size();i++)
      cout<<S[i]+1<<" ";
   return 0;
}

输出：

输入顶点数：4
输入边数：5
Enter the end-points of edge 1 : 2 1
Enter the end-points of edge 2 : 3 2
Enter the end-points of edge 3 : 4 3
Enter the end-points of edge 4 : 1 4
Enter the end-points of edge 5 : 1 3
The required vertex cover is as follows:
1 2 3 4

以上是 C ++程序实现启发式以查找图形的顶点覆盖 的全部内容， 来源链接： utcz.com/z/322068.html

回到顶部