判断同构数 c语言程序(java人脸识别算法)

大家好，又见面了，我是你们的朋友全栈君。

图的同构识别：

给定的两个邻接矩阵，判断其三个必要非充分条件：
①结点数目相同
②变数相同
③度数相同的结点数相同
以①②③为前提进行矩阵变换，看给定的两个矩阵中，其中的一个矩阵是否能变换为另一个矩阵;

阅读文章前需要知道一个概念:
邻接矩阵中的结点的次序是有实际意义的，当结点进行行变换的时候，必须对其对应的列也进行变换
温馨提示：
博客前两片示例代码段是有小瑕疵的
实现代码和说明:

#include<iostream>
#include<stdlib.h>
#define MAX 100 
using namespace std;
struct AdjacencyMatrix{ 
//邻接矩阵
int points;             //邻接矩阵的顶点个数（即矩阵阶数）
int edges;              //邻接矩阵的边的条数（即邻接矩阵非零点个数/2）
int Matrix[MAX][MAX];   //矩阵
int weight[MAX];        //行和度数的集合
};
AdjacencyMatrix A,B;//定义邻接矩阵A、B，将A调整成B且满足同构的必要条件则A、B同构
//三个必要条件 ① 结点数相同 ②边数相同 ③ 度数相同的结点数相同 
// (行进行交换)
//行位置交换函数，返回true为正常交换,这里的行列交换都是针对于图A的 
bool SwapRows(int i,int j){ 

int k;
//进行 行交换
for(k=0;k<A.points;k++){ 
//矩阵的i 行和j行进行交换 
int temp;
temp = A.Matrix[i][k];
A.Matrix[i][k]= A.Matrix[j][k];
A.Matrix[j][k]= temp;
}
int temp;
//行交换了，度也要跟着交换
//这种操作，相当于把点进行移动，移动到某个位置，
//相当于三维世界的直接拖动，即：他的点本来是堆叠起来的(或者次序不当)，然后我们将他的点散开(或者移动)，重新按照某种规则进行摆放(这种规则让当前图的结构(矩阵)趋近于目标图)
//行交换完毕后其度也要记得改变 
temp =A.weight[i];
A.weight[i]= A.weight[j];
A.weight[j]= temp; 
return true;
} 
//(列交换)
//列位置交换函数，返回true为正常交换，false为无法交换
bool  SwapColumns(int currentLayer,int i,int j){ 
//为什么三个参数呢 : 为了保持前面修改的趋势 不被改变 
int k;
//判断是否能交换
//这个循环的意思是，我之前从第一行开始，我们的图A尽量与图B相同，然后，currentLayer是当前的层次
//可以理解为同步到当前层次了，然后，如果我们的列 交换，如果它们不相同,则 会破坏我们之前 尽量 与 图B 结构 靠近 的这个趋势的话,我们是不能让它继续进行下去的
//因为如果我们 前面 图A和图B同步了第一行，然后图A在与图B的其他行进行 同步的时候，发现，如果交换的结果会影响到之前的同步结果的话
//那么这样就没法同构了,也就是这两个矩阵，不可能相同 
for(k=0;k<currentLayer;k++){ 
//第i列和第j列进行调换
if(A.Matrix[k][i]!=A.Matrix[k][j]){ 

//无法交换，因为交换后会影响先前调整的结果，故而不同构
return false; 
}
}
//进行列交换
for(k=0;k<A.points;k++){ 

int temp;
temp =A.Matrix[k][i];
A.Matrix[k][i]= A.Matrix[k][j];
A.Matrix[k][j]= temp;
} 
return true;
} 
//用于快速排序的比较算法
int cmp( const void *a , const void *b ){ 
 
return *(int *)a - *(int *)b; 
}
int main(){ 

cout<<"请输入两个图的阶数（顶点数）："<<endl;
cin>>A.points>>B.points;
//判断第一个必要条件
if(A.points!=B.points){ 

cout<<"阶数不同！不同构！"<<endl;
return 0;
}
cout<<"请输入第1个图的邻接矩阵："<<endl;
A.edges = 0;
B.edges = 0;
//用邻接矩阵方式输入A、B矩阵
int i,j,k,y;
for(i=0;i<A.points;i++){ 

for(j=0;j<A.points;j++){ 

cin>>A.Matrix[i][j];
if(A.Matrix[i][j]==1){ 

A.edges++;
}   
}
}
cout<<"请输入第2个图的邻接矩阵："<<endl;
for(i=0;i<B.points;i++){ 

for(j=0;j<B.points;j++){ 

cin>>B.Matrix[i][j];
if(B.Matrix[i][j]==1){ 

B.edges++;
}   
}
}
//判断第二个必要条件
if(A.edges!=B.edges){ 

cout<<"边的条数不同！不同构！"<<endl;
return 0;   
} 
//因为是邻接矩阵，所以边的条数（即邻接矩阵非零点个数/2）
//在给边进行赋值的时候，我们在二维 矩阵的值是1的时候都给边+1了，因为是无向图，G[i][j]和G[j][i] 是一样的，因此要/2 
A.edges =A.edges/2;
B.edges =B.edges/2;
int Aweight[MAX];//MAX==100 
int Bweight[MAX];
//判断第三个必要条件
int x=0;
for(k=0;k<A.points;k++){ 
//A图 共有 point 个点，然后对这些点的度数进行计算 
int count=0;//初始化度为0 
for(y=0;y<A.points;y++){ 

if(A.Matrix[k][y]==1){ 
 //有边，度+1,这里不用考虑 要/2 ,因为是针对当前点k而言的,A.Matrix[k][y]==1就说明 k对于y点(变点)而言有边 
count++;//度+1 
}
}
Aweight[x]= count;//遍历完说有点，统计度后,将其记录在一个一维数组中 
A.weight[x++]=count;//当然，需要将当前的度记录在A 数据结构中的 weight数组中，然后x+1;
} 
qsort(Aweight,A.points,sizeof(Aweight[0]),cmp);
//调用系统快速排序算法
//进行排序的意义是: 因为 第一个点的度是不确定的，因此，我们值能将这个数组进行从小到大（或者从大到小）进行排序，排序完后，数组就是有规律的了
//然后将 B图 记录 点度数的数组也进行从小到大（或者从大到小）进行排序，排序完后，看是否满足 :
//同构图的三个必要条件中的第三个条件:度数相同的节点个数相同
x=0;
//对矩阵B也进行相同的操作 
for(k=0;k<B.points;k++){ 

int count=0;
for(y=0;y<B.points;y++){ 

if(B.Matrix[k][y]==1){ 

count++;
}
}
Bweight[x]= count;
B.weight[x++]=count;
}
qsort(Bweight,B.points,sizeof(Bweight[0]),cmp);//调用系统快速排序算法
//判断是否满足第三个条件 
for(k=0;k<A.points;k++){ 

if(Aweight[k]!=Bweight[k]){ 

cout<<"边的度数不同！不同构！"<<endl;
return 0;
}
}
//进行矩阵变换 
//三个条件都满足，则进行最后的验证操作:将第一个图的矩阵进行变换，让其结构趋近于第二个图
//并且如果操作过程没有被因为 行列交换操作 判断出错而打断(就是不能行列交换，如何行列交换都无法变换成第二个图,进而被打断)
//调整A矩阵成B 请注意:以下操作 列交换 必定伴随着 行的交换 为什么呢: 因为，虽然矩阵的行和列 之间没有太大的关联，即便行交换和列交换并不会改变其点之间的映射关系
//也没有说 行交换后列必须得交换，但是，在表示图的矩阵中，点的次序是有含义的; 
for(i=0;i<B.points;i++){ 

for(j=i;j<A.points;j++){ 

//找到度相同
//对度数相同的结点进行行交换 
if(B.weight[i] == A.weight[j]){ 
//注意，这里是B的度等于 A的度的时候 
//进行行交换
if(i!=j){ 
//如果i!=j就交换，否则跳过(不用交换，换了和没换一样) 
SwapRows(i,j);//先交换行 注意:行进行交换了之后，对应的列也必须跟着变化(可以理解为行和列结点的顺序必须保持一致) 
}
//进行列交换 从上往下,以 i 为行 不断的 向第二个图的结构靠近 
if(i!=j){ 

if(SwapColumns(i,i,j)==false){ 
//交换列 
cout<<"无法调整成相同的邻接矩阵！不同构！"<<endl;
return 0;
}       
int list[MAX];
x=0;
//判断非零顶点所处列的位置是否相同
//两个for循环是在i!=j的情况下执行的
for(k=0;k<A.points;k++){ 
//找出位置不同的点放入list 
if(A.Matrix[i][k]!=B.Matrix[i][k]){ 
//找出A图中与B不相同的位置，记录在list中 
list[x]=k;//记录不同的列 
x=x+1;
}
}
for(k=0;k<x;k=k+2){ 

if(SwapColumns(i,list[k],list[k+1])==false){ 
//列交换 伴随着 行交换 
//0 1/2 3/4 5
cout<<"无法调整成相同的邻接矩阵！不同构！"<<endl;
return 0;
}//循环交换列 
SwapRows(list[k],list[k+1]);//循环交换行 
}
}
break; 
} 
}
}
cout<<"经过检测，两图同构！"<<endl;
return 0;
}

举例:
图G和图G’其矩阵的变换过程如下图:

最终图G通过移动点的位置，有了与目标图一样的结构，并且其可视化为

然后对比目标图G‘

我们可以发现，只要变换图G将其结点b与1对应，c与2对应，a与3对应，d与4对应的时候，其结构就可以清楚的看出来两个图的一样的，也就是同构的，其邻接矩阵也是相同的，邻接矩阵的行列也是这样的映射关系
b:1
c:2
a:3
d:4
因此，应了前文那句话，邻接矩阵中的结点的次序是有实际意义的，当结点进行行变换的时候，必须对其对应的列也进行变换.

代码存在的缺点:

对于同构图G’和G‘’

其运行结果：

对代码进行优化、改进

(其实还是有问题???，读者可以忽略改进的代码，直接跳到最后看没有正确的代码,因为代码记录了我对图的同构的理解的过程，因此，不删掉这两段错误的代码)
这是以上代码存在的问题，现对以上代码做优化、改进；
思路如下:
①我们对图G的结构进行调整:
让其每一行的度调整至G‘,也就是对图G的点，也就是在矩阵中对行列进行移动;
②调整完毕,立刻检查两个矩阵是否相同,若不同，从上往下，调换度相同的结点，遍历所有的可能，每次调换完毕，都检查一次，看是否两个矩阵相同
因此，对函数添加如下代码:
①:
一个中间数组C,(如果这种初始判定条件下，仍然返回false的话，进行后续的判定，而后续的判定需要一个最初始状态的数组A)
注意，这个数组必须也初始化与A相同的度
(不初始化就为0无法判断是否同构)
②:
让第一个图的矩阵的度和第二个图的度保持一致的函数to_be_similar():

 void to_be_similar(){ 

for(i=0;i<B.points;i++){ 

for(j=i;j<C.points;j++){ 
    
if(B.weight[i] == C.weight[j]){ 
//注意，这里是B的度等于 A的度的时候 
//进行行交换
if(i!=j){ 
//如果i!=j就交换，否则跳过(不用交换，换了和没换一样) 
SwapRows(i,j);//先交换行 注意:行进行交换了之后，对应的列也必须跟着变化(可以理解为行和列结点的顺序必须保持一致) 
SwapColumns(0,i,j);//行变化一定伴随列变化 
}
}
}
}
}//执行完毕这个函数，那么，这两个矩阵的度的结构就一样了 
//(C矩阵度的赋值并不在这里哦)

③:判定函数Judge():

 bool Judge(){ 

for(i =0; i <C.points;i++){ 

for(j=0; j <B.points;j++){ 

if(C.Matrix[i][j]!=B.Matrix[i][j])
return false;
}
}
return true;
}

④交换行中度相同的函数并且行交换后列也交换，在交换前判定，交换完毕判定的函数SwapColumnsAndRowsAndJudge():

 bool SwapColumnsAndRowsAndJudge(){ 
//直接根据点的度相同，进行列交换 每次交换完行列，都要进行判定：两个矩阵是否相同 
for(int x=0;x<C.points;x++){ 

//交换前进行判断 
if(Judge()){ 

return true;
}
for(y=x;y<C.points;y++){ 
//不用回到之前判断的状态了，所以这里y=x 
if(x!=y&&C.weight[x]==C.weight[y]){ 
//&&x!=y
SwapRowsTwo(x,y);
SwapColumnsTwo(x,y);
}
if(Judge()){ 

return true;
}
}
return false;
}
}

⑤新增加的两个行列置换函数(直接换)
SwapRowsTwo():

bool SwapRowsTwo(int i,int j){ 
//改进代码 
int k;
for(k=0;k<C.points;k++){ 
//矩阵的i 行和j行进行交换 
int temp;
temp = C.Matrix[i][k];
C.Matrix[i][k]= C.Matrix[j][k];
C.Matrix[j][k]= temp;
}
int temp;
temp =C.weight[i];
C.weight[i]= C.weight[j];
C.weight[j]= temp; 
return true;
}

⑥SwapColumnsTwo():

SwapColumnsTwo(int i,int j){ 
//改进代码 
int k;
for(k=0;k<C.points;k++){ 

int temp;
temp =C.Matrix[k][i];
C.Matrix[k][i]= C.Matrix[k][j];
C.Matrix[k][j]= temp;
} 
return true;
}

完整代码如下:

#include<iostream>
#include<stdlib.h>
#define MAX 100 
using namespace std;
struct AdjacencyMatrix{ 
//邻接矩阵
int points;             //邻接矩阵的顶点个数（即矩阵阶数）
int edges;              //邻接矩阵的边的条数（即邻接矩阵非零点个数/2）
int Matrix[MAX][MAX];   //矩阵
int weight[MAX];        //行和度数的集合
};
int i,j,k,y;
AdjacencyMatrix A,B,C;//定义邻接矩阵A、B，将A调整成B且满足同构的必要条件则A、B同构
//三个必要条件 ① 结点数相同 ②边数相同 ③ 度数相同的结点数相同 
// (行进行交换)
//行位置交换函数，返回true为正常交换,这里的行列交换都是针对于图A的 
bool SwapRows(int i,int j){ 

int k;
//进行 行交换
for(k=0;k<A.points;k++){ 
//矩阵的i 行和j行进行交换 
int temp;
temp = A.Matrix[i][k];
A.Matrix[i][k]= A.Matrix[j][k];
A.Matrix[j][k]= temp;
}
int temp;
//行交换了，度也要跟着交换
//这种操作，相当于把点进行移动，移动到某个位置，
//相当于三维世界的直接拖动，即：他的点本来是堆叠起来的(或者次序不当)，然后我们将他的点散开(或者移动)，重新按照某种规则进行摆放(这种规则让当前图的结构(矩阵)趋近于目标图)
//行交换完毕后其度也要记得改变 
temp =A.weight[i];
A.weight[i]= A.weight[j];
A.weight[j]= temp; 
return true;
}
bool SwapRowsTwo(int i,int j){ 
//改进代码 
int k;
for(k=0;k<C.points;k++){ 
//矩阵的i 行和j行进行交换 
int temp;
temp = C.Matrix[i][k];
C.Matrix[i][k]= C.Matrix[j][k];
C.Matrix[j][k]= temp;
}
int temp;
temp =C.weight[i];
C.weight[i]= C.weight[j];
C.weight[j]= temp; 
return true;
}
bool  SwapColumnsTwo(int i,int j){ 
//改进代码 
int k;
for(k=0;k<C.points;k++){ 

int temp;
temp =C.Matrix[k][i];
C.Matrix[k][i]= C.Matrix[k][j];
C.Matrix[k][j]= temp;
} 
return true;
} 
//(列交换)
//列位置交换函数，返回true为正常交换，false为无法交换
bool  SwapColumns(int currentLayer,int i,int j){ 
//为什么三个参数呢 : 为了保持前面修改的趋势 不被改变 
int k;
//判断是否能交换
//这个循环的意思是，我之前从第一行开始，我们的图A尽量与图B相同，然后，currentLayer是当前的层次
//可以理解为同步到当前层次了，然后，如果我们的列 交换，如果它们不相同,则 会破坏我们之前 尽量 与 图B 结构 靠近 的这个趋势的话,我们是不能让它继续进行下去的
//因为如果我们 前面 图A和图B同步了第一行，然后图A在与图B的其他行进行 同步的时候，发现，如果交换的结果会影响到之前的同步结果的话
//那么这样就没法同构了,也就是这两个矩阵，不可能相同 
for(k=0;k<currentLayer;k++){ 
//第i列和第j列进行调换
if(A.Matrix[k][i]!=A.Matrix[k][j]){ 

//无法交换，因为交换后会影响先前调整的结果，故而不同构
return false; 
}
}
//进行列交换
for(k=0;k<A.points;k++){ 

int temp;
temp =A.Matrix[k][i];
A.Matrix[k][i]= A.Matrix[k][j];
A.Matrix[k][j]= temp;
} 
return true;
} 
void to_be_similar(){ 

for(i=0;i<B.points;i++){ 

for(j=i;j<C.points;j++){ 
    
if(B.weight[i] == C.weight[j]){ 
//注意，这里是B的度等于 A的度的时候 
//进行行交换
if(i!=j){ 
//如果i!=j就交换，否则跳过(不用交换，换了和没换一样) 
SwapRowsTwo(i,j);//先交换行 注意:行进行交换了之后，对应的列也必须跟着变化(可以理解为行和列结点的顺序必须保持一致) 
SwapColumnsTwo(i,j);//行变化一定伴随列变化 
}
break;
}
}
}
}//执行完毕这个函数，那么，这两个矩阵的度的结构就一样了 
bool Judge(){ 

for(i =0; i <C.points;i++){ 

for(j=0; j <B.points;j++){ 

if(C.Matrix[i][j]!=B.Matrix[i][j])
return false;
}
}
return true;
}
bool SwapColumnsAndRowsAndJudge(){ 
//直接根据点的度相同，进行列交换 每次交换完行列，都要进行判定：两个矩阵是否相同 
for(int x=0;x<C.points;x++){ 

//交换前进行判断 
if(Judge()){ 

return true;
}
for(y=x;y<C.points;y++){ 
//不用回到之前判断的状态了，所以这里y=x 
if(x!=y&&C.weight[x]==C.weight[y]){ 
//&&x!=y
SwapRowsTwo(x,y);
SwapColumnsTwo(x,y);
}
if(Judge()){ 

return true;
}
}
return false;
}
} 
//用于快速排序的比较算法
int cmp( const void *a , const void *b ){ 
 
return *(int *)a - *(int *)b; 
}
int main(){ 

cout<<"请输入两个图的阶数（顶点数）："<<endl;
cin>>A.points>>B.points;
C.points=A.points;//注意这里要初始化 
//判断第一个必要条件
if(A.points!=B.points){ 

cout<<"阶数不同！不同构！"<<endl;
return 0;
}
cout<<"请输入第1个图的邻接矩阵："<<endl;
A.edges = 0;
B.edges = 0;
//用邻接矩阵方式输入A、B矩阵
for(i=0;i<A.points;i++){ 

for(j=0;j<A.points;j++){ 

cin>>A.Matrix[i][j];
C.Matrix[i][j]=A.Matrix[i][j];//拷贝A到C，用C进行分析 
if(A.Matrix[i][j]==1){ 

A.edges++;
}   
}
}
cout<<"请输入第2个图的邻接矩阵："<<endl;
for(i=0;i<B.points;i++){ 

for(j=0;j<B.points;j++){ 

cin>>B.Matrix[i][j];
if(B.Matrix[i][j]==1){ 

B.edges++;
}   
}
}
//判断第二个必要条件
if(A.edges!=B.edges){ 

cout<<"边的条数不同！不同构！"<<endl;
return 0;   
} 
//因为是邻接矩阵，所以边的条数（即邻接矩阵非零点个数/2）
//在给边进行赋值的时候，我们在二维 矩阵的值是1的时候都给边+1了，因为是无向图，G[i][j]和G[j][i] 是一样的，因此要/2 
A.edges =A.edges/2;
B.edges =B.edges/2;
int Aweight[MAX];//MAX==100 
int Bweight[MAX];
//判断第三个必要条件
int x=0;
for(k=0;k<A.points;k++){ 
//A图 共有 point 个点，然后对这些点的度数进行计算 
int count=0;//初始化度为0 
for(y=0;y<A.points;y++){ 

if(A.Matrix[k][y]==1){ 
 //有边，度+1,这里不用考虑 要/2 ,因为是针对当前点k而言的,A.Matrix[k][y]==1就说明 k对于y点(变点)而言有边 
count++;//度+1 
}
}
Aweight[x]= count;//遍历完说有点，统计度后,将其记录在一个一维数组中 
C.weight[x]= A.weight[x]=count;//当然，需要将当前的度记录在A 数据结构中的 weight数组中，然后x+1;
x=x+1;
} 
qsort(Aweight,A.points,sizeof(Aweight[0]),cmp);
//调用系统快速排序算法
//进行排序的意义是: 因为 第一个点的度是不确定的，因此，我们值能将这个数组进行从小到大（或者从大到小）进行排序，排序完后，数组就是有规律的了
//然后将 B图 记录 点度数的数组也进行从小到大（或者从大到小）进行排序，排序完后，看是否满足 :
//同构图的三个必要条件中的第三个条件:度数相同的节点个数相同
x=0;
//对矩阵B也进行相同的操作 
for(k=0;k<B.points;k++){ 

int count=0;
for(y=0;y<B.points;y++){ 

if(B.Matrix[k][y]==1){ 

count++;
}
}
Bweight[x]= count;
B.weight[x++]=count;
}
qsort(Bweight,B.points,sizeof(Bweight[0]),cmp);//调用系统快速排序算法
//判断是否满足第三个条件 
for(k=0;k<A.points;k++){ 

if(Aweight[k]!=Bweight[k]){ 

cout<<"边的度数不同！不同构！"<<endl;
return 0;
}
}
//矩阵可能一开始就是同构的，然后，因为点的次序不同，而导致矩阵不相同，此时，我们只需要将矩阵进行行列交换，遍历所有的可能，看是否能够达到两个矩阵相同的效果
to_be_similar();
if(	SwapColumnsAndRowsAndJudge()){ 

cout<<"经检测，两个图同构!"<<endl;
return 0;
}	
//进行矩阵变换 
//三个条件都满足，则进行最后的验证操作:将第一个图的矩阵进行变换，让其结构趋近于第二个图
//并且如果操作过程没有被因为 行列交换操作 判断出错而打断(就是不能行列交换，如何行列交换都无法变换成第二个图,进而被打断)
//调整A矩阵成B 请注意:以下操作 列交换 必定伴随着 行的交换 为什么呢: 因为，虽然矩阵的行和列 之间没有太大的关联，即便行交换和列交换并不会改变其点之间的映射关系
//也没有说 行交换后列必须得交换，但是，在表示图的矩阵中，点的次序是有含义的; 
for(i=0;i<B.points;i++){ 

for(j=i;j<A.points;j++){ 

//找到度相同
//对度数相同的结点进行行交换 
if(B.weight[i] == A.weight[j]){ 
//注意，这里是B的度等于 A的度的时候 
//进行行交换
if(i!=j){ 
//如果i!=j就交换，否则跳过(不用交换，换了和没换一样) 
SwapRows(i,j);//先交换行 注意:行进行交换了之后，对应的列也必须跟着变化(可以理解为行和列结点的顺序必须保持一致) 
}
//进行列交换 从上往下,以 i 为行 不断的 向第二个图的结构靠近 
if(i!=j){ 

if(SwapColumns(i,i,j)==false){ 
//交换列 
cout<<"无法调整成相同的邻接矩阵！不同构！"<<endl;
return 0;
}       
int list[MAX];
x=0;
//判断非零顶点所处列的位置是否相同
//两个for循环是在i!=j的情况下执行的
for(k=0;k<A.points;k++){ 
//找出位置不同的点放入list 
if(A.Matrix[i][k]!=B.Matrix[i][k]){ 
//找出A图中与B不相同的位置，记录在list中 
list[x]=k;//记录不同的列 
x=x+1;
}
}
for(k=0;k<x;k=k+2){ 

if(SwapColumns(i,list[k],list[k+1])==false){ 
//列交换 伴随着 行交换 
//0 1/2 3/4 5
cout<<"无法调整成相同的邻接矩阵！不同构！"<<endl;
return 0;
}//循环交换列 
SwapRows(list[k],list[k+1]);//循环交换行 
}
}
break; 
} //这里是i!=j的时候他就会修改交换,然后我想如果度相同，我们是否也可以进行行列交换呢 
}
}
cout<<"经过检测，两图同构！"<<endl;
return 0;
}

测试图
G’和G’‘

矩阵变化流程:

测试数据
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 0
0 0 0 1 0 0

0 1 0 0 0 0
1 0 1 0 0 1
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0

测试结果：

测试G和G‘:

测试数据:
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 1
0 0 1 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0

0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 0
0 0 0 1 0 0

算法的时间复杂度和空间复杂度

由代码:
O(T1)=N^2

O(T2)=N*logN

O(T3)=N^2

O(T4)=N*logN

O(T5)=N

O(T6)=N^ 2* N+N^ 2 * (N+N)= N^3

O(T7)=N^2 *N=N ^3 //外面有两层for 循环加上这里的就变成N ^3

假设有k=N ，则这一层的for 循环的执行次数是:N/2
SwapColumns函数若currentLayer为N则SwapColumns的执行次数为:
N+N；
SwapRows函数的执行次数为N;
因此由这一层for循环即 for(k=0;k<x;k=k+2) 的时间复杂度为N/2*(N+N)=N^2
由于外面还有两层for循环,因此这里的时间复杂度为 O(T8)=N^4

O(T9)=N*N^2=N ^3
因此其时间复杂度为:
O(T)=O(T1)+……+O(T9)=N^4
以上两片段代码还是有问题的，因为没有考虑到全排列这种最坏的情况：
如果矩阵中所有的度都一样，这种情况怎么办呢？直接度相同就交换吗？
改进的代码中只考虑了度相同就交换，但是，交换后，是不是忽略了什么，比如，其他列的排列情况做变换？即：第一行与另外一度相同的行交换了，那么，除第一行外，其他行都全排列一下才能够遍历所有可能。

仅仅靠两层循环是不能够遍历所有可能的

因此，最后再对代码进行改进，在两个待判定的图的三个必要不充分条件满足后，直接对其中一个矩阵进行全排列，看是否和目标矩阵相同，相同则输出同构，否则输出不同构。

分析出问题，对代码做最后的完善.

全排列判断代码如下：

#include<iostream>
#include<stdlib.h>
#define MAX 100 
using namespace std;
struct AdjacencyMatrix{ 
//邻接矩阵
int points;             //邻接矩阵的顶点个数（即矩阵阶数）
int edges;              //邻接矩阵的边的条数（即邻接矩阵非零点个数/2）
int Matrix[MAX][MAX];   //矩阵
int weight[MAX];        //行和度数的集合
};
int i,j,k,y,p=0;
AdjacencyMatrix A,B;//定义邻接矩阵A、B，将A调整成B且满足同构的必要条件则A、B同构
//三个必要条件 ① 结点数相同 ②边数相同 ③ 度数相同的结点数相同 
// (行进行交换)
//行位置交换函数，返回true为正常交换,这里的行列交换都是针对于图A的 
bool SwapRows(int i,int j){ 
//改进代码 
int k;
for(k=0;k<A.points;k++){ 
//矩阵的i 行和j行进行交换 
int temp;
temp = A.Matrix[i][k];
A.Matrix[i][k]= A.Matrix[j][k];
A.Matrix[j][k]= temp;
}
int temp;
temp =A.weight[i];
A.weight[i]= A.weight[j];
A.weight[j]= temp; 
return true;
}
bool  SwapColumns(int i,int j){ 
//改进代码 
int k;
for(k=0;k<A.points;k++){ 

int temp;
temp =A.Matrix[k][i];
A.Matrix[k][i]= A.Matrix[k][j];
A.Matrix[k][j]= temp;
} 
return true;
} 
int fac(int x)  //阶乘计算 
{ 
  
register int i,f=1;  
for(i=1;i<=x;i++)  
f*=i;  
return f;  
}  
bool Judge(){ 

for(i =0; i <A.points;i++){ 

for(j=0; j <B.points;j++){ 

if(A.Matrix[i][j]!=B.Matrix[i][j])
return false;
}
}
return true;
}
bool permutation( int k, int m,int total_number)
{ 

int i, j;
if (k == m)//k==m的时候就是一种可能 
{ 
		
++p;
if(p==total_number){ 

return false;
}
}
else
{ 

for (j = k; j <= m; j++)
{ 

SwapRows(j,k);
SwapColumns(j,k);
if(Judge()){ 

return true;
}
permutation( k + 1, m,total_number);	
SwapRows(j,k);//换回来 
SwapColumns(j,k);//换回来，在前面变换的基础上继续遍历其他可能。 
if(p==total_number){ 

return false;//for循环里也要添加判断 
}
}
}
}
//用于快速排序的比较算法
int cmp( const void *a , const void *b ){ 
 
return *(int *)a - *(int *)b; 
}
int main(){ 

cout<<"请输入两个图的阶数（顶点数）："<<endl;
cin>>A.points>>B.points;
//判断第一个必要条件
int total_number=fac(A.points);//初始化阶乘所需要最大次数的值. 
if(A.points!=B.points){ 

cout<<"阶数不同！不同构！"<<endl;
return 0;
}
cout<<"请输入第1个图的邻接矩阵："<<endl;
A.edges = 0;
B.edges = 0;
//用邻接矩阵方式输入A、B矩阵
for(i=0;i<A.points;i++){ 

for(j=0;j<A.points;j++){ 

cin>>A.Matrix[i][j];
if(A.Matrix[i][j]==1){ 

A.edges++;
}   
}
}
cout<<"请输入第2个图的邻接矩阵："<<endl;
for(i=0;i<B.points;i++){ 

for(j=0;j<B.points;j++){ 

cin>>B.Matrix[i][j];
if(B.Matrix[i][j]==1){ 

B.edges++;
}   
}
}
//判断第二个必要条件
if(A.edges!=B.edges){ 

cout<<"边的条数不同！不同构！"<<endl;
return 0;   
} 
//因为是邻接矩阵，所以边的条数（即邻接矩阵非零点个数/2）
//在给边进行赋值的时候，我们在二维 矩阵的值是1的时候都给边+1了，因为是无向图，G[i][j]和G[j][i] 是一样的，因此要/2 
A.edges =A.edges/2;
B.edges =B.edges/2;
int Aweight[MAX];//MAX==100 
int Bweight[MAX];
//判断第三个必要条件
int x=0;
for(k=0;k<A.points;k++){ 
//A图 共有 point 个点，然后对这些点的度数进行计算 
int count=0;//初始化度为0 
for(y=0;y<A.points;y++){ 

if(A.Matrix[k][y]==1){ 
 //有边，度+1,这里不用考虑 要/2 ,因为是针对当前点k而言的,A.Matrix[k][y]==1就说明 k对于y点(变点)而言有边 
count++;//度+1 
}
}
Aweight[x]= count;//遍历完说有点，统计度后,将其记录在一个一维数组中 
x=x+1;
} 
qsort(Aweight,A.points,sizeof(Aweight[0]),cmp);
//调用系统快速排序算法
//进行排序的意义是: 因为 第一个点的度是不确定的，因此，我们值能将这个数组进行从小到大（或者从大到小）进行排序，排序完后，数组就是有规律的了
//然后将 B图 记录 点度数的数组也进行从小到大（或者从大到小）进行排序，排序完后，看是否满足 :
//同构图的三个必要条件中的第三个条件:度数相同的节点个数相同
x=0;
//对矩阵B也进行相同的操作 
for(k=0;k<B.points;k++){ 

int count=0;
for(y=0;y<B.points;y++){ 

if(B.Matrix[k][y]==1){ 

count++;
}
}
Bweight[x]= count;
B.weight[x++]=count;
}
qsort(Bweight,B.points,sizeof(Bweight[0]),cmp);//调用系统快速排序算法
//判断是否满足第三个条件 
for(k=0;k<A.points;k++){ 

if(Aweight[k]!=Bweight[k]){ 

cout<<"边的度数不同！不同构！"<<endl;
return 0;
}
}
//矩阵可能一开始就是同构的，然后，因为点的次序不同，而导致矩阵不相同，此时，我们只需要将矩阵进行行列交换，遍历所有的可能，看是否能够达到两个矩阵相同的效果 
if(permutation(0,(A.points-1),total_number)){ 
//矩阵全排列 
cout<<"经检测，两个图同构!"<<endl;
}else{ 

cout<<"不同构！"<<endl;
} 
return 0;
}

测试样例：

测试数据:
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 0
0 0 0 1 0 0
………………………
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
测试结果

再测试一下前面测试过的G和G’

测试数据
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 0
0 0 0 1 0 0
……………………
0 1 0 0 0 0
1 0 1 0 0 1
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0
测试结果: