数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究C++ 程序实现寻找图的顶点覆盖的试探法
图的顶点覆盖是找到一组顶点 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<<"Enter number of vertices:";
cin>>n;
cout<<"Enter number of Edges:";
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;
}输出
Enter number of vertices:4 Enter number of Edges: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
更新于： 30-Jul-2019
646 人浏览
广告