判断一个图是否为二部图的程序
#include#include#include#includeusing namespace std;const int N=205;int flag[N];int map[N][N];int match[N];bool link[N];int n,m;int bfs(){ int j; memset(flag,-1,sizeof(flag)); for(j=1;j q; flag[j]=1; q.push(j); while(!q.empty()) { int k=q.front(); q.pop(); for(int i=1;i#include #include #define maxn 305using namespace std;vector G[maxn];int vis[maxn];bool dfs(int u,bool f){ if(vis[u]>=0) { if(vis[u]==f) return true; else return false; } vis[u]=f; for(int i=0;i<3;i++) { if(!dfs(G[u][i],f^1)) return false; } return true;}int main(){int v,x,y; //v是顶点数，x是一条边的起点，y是终点printf(“请输入顶点数: “); while(scanf("%d",&v)==1)//如果输入的个数不为1，跳出循环 { if(!v)break; for(int i=0;i<v;i++) G[i].clear(); //设置了v个向量，并将全部容器清空 memset(vis,-1,sizeof(vis)); //将vis数组全部置为 -1 while(scanf("%d%d",&x,&y)==2) { if(!x&&!y)break; x--;y--; G[x].push_back(y); //在容器map[x]的尾部插入y，从而建立一个无向图 G[y].push_back(x); //在容器map[y]的尾部插入x，从而建立一个无向图 } if(dfs(0,1)) //如果相邻的两点的颜色不相同，则是二分图 { printf("输入的图是二分图\n"); } else { printf("输入的图不是二分图\n"); } } return 0;}intwarshall(inta[N][N]){ intcol =0; intline =0; inttemp =0; for(col =0;col <N;col++){ for(line =0;line <N;line++){ if(a[line][col]!=0){ for(temp =0;temp <N;temp++){ a[line][temp]=a[line][temp]|a[col][temp]; } } } } return TRUE;}
如何判断两个图是否同构
1、两个图的顶点集合之间能够建立一一对应的映射,对应的顶点之间保持边的一一对应关系。2、也可以通过图的邻接矩阵来探讨.一个图的邻接矩阵经过有限次的互换行或列的变换变成另一个图的邻接矩阵,则两个图同构。同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若两个数学结构之间存在同构映射，那么这两个结构叫做“是同构的”。一般来说，如果忽略同构对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的。扩展资料：目的在数学中研究同构的主要目的是为了把数学理论应用于不同的领域。如果两个结构是同构的，那么其上的对象会有相似的属性和操作，对某个结构成立的命题在另一个结构上也就成立。因此，如果在某个数学领域发现了一个对象结构同构于某个结构，且对于该结构已经证明了很多定理，那么这些定理马上就可以应用到该领域。如果某些数学方法可以用于该结构，那么这些方法也可以用于新领域的结构。这就使得理解和处理该对象结构变得容易，并往往可以让数学家对该领域有更深刻的理解。参考资料来源：百度百科-同构
