给我一个基于c++的有关图的同构问题的代码,其中判断图的顶点数是否相同,顶点的度是否相同
时间: 2023-12-03 08:43:26 浏览: 137
以下是一个基于C++的图同构问题的代码,其中包括了判断图的顶点数是否相同和顶点的度是否相同。
```
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,m,x,y,d1[N],d2[N],h1[N],h2[N],vis1[N],vis2[N];
struct edge{
int next,to;
}e1[N],e2[N];
void add1(int x,int y){
e1[++m].next=h1[x];
e1[m].to=y;
h1[x]=m;
}
void add2(int x,int y){
e2[++m].next=h2[x];
e2[m].to=y;
h2[x]=m;
}
void dfs1(int x,int fa){
vis1[x]=1;
for(int i=h1[x];i;i=e1[i].next){
int y=e1[i].to;
if(y==fa||vis1[y])continue;
dfs1(y,x);
}
}
void dfs2(int x,int fa){
vis2[x]=1;
for(int i=h2[x];i;i=e2[i].next){
int y=e2[i].to;
if(y==fa||vis2[y])continue;
dfs2(y,x);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
add1(x,y);
add1(y,x);
}
for(int i=1;i<=n;i++){
if(!vis1[i]){
dfs1(i,0);
break;
}
}
for(int i=1;i<=n;i++){
if(!vis2[i]){
dfs2(i,0);
break;
}
}
int flag1=1;
int flag2=1;
for(int i=1;i<=n;i++){
d1[i]=d2[i]=0;
for(int j=h1[i];j;j=e1[j].next)d1[i]++;
for(int j=h2[i];j;j=e2[j].next)d2[i]++;
if(d1[i]!=d2[i])flag1=0;
if(!vis1[i]||!vis2[i])flag2=0;
}
if(flag1&&flag2)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
```
首先,我们将图用邻接表的形式存储,然后利用深度优先搜索来遍历两个图,并标记已经访问过的节点。
接着,我们计算每个节点的度数,并判断它们是否相等。如果所有节点的度数都相等,则说明顶点的度数相同。
最后,我们检查是否所有节点都被访问过。如果是,那么说明图的顶点数也相同。如果不是,那么说明顶点数不同。
如果顶点数和度数都相等,则输出“Yes”,否则输出“No”。
阅读全文