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

给定的两个邻接矩阵,判断其三个必要非充分条件:①结点数目相同②变数相同③度数相同的结点数相同以①②③为前提进行矩阵变换,看给定的两个矩阵中,其中的一个矩阵是否能变换为另一个矩阵;实现代码和说明:#include<iostream>#include<stdlib.h>#defineMAX100usingnamespacestd;structAdjacencyMatrix{//邻接矩阵intpoints;/

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

图的同构识别:

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

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

实现代码和说明:

#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通过移动点的位置,有了与目标图一样的结构,并且其可视化为
判断同构数 c语言程序(java人脸识别算法)
然后对比目标图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
测试结果:
在这里插入图片描述

因为考虑到矩阵的比较和全排列问题(这才是最坏的情况) 矩阵比较:两个矩阵每个元素都比较一遍 需要N^2,因此,每比较一次都 是N ^2 全排列: 让矩阵行列变化,遍历所有的可能(最坏的情况),也就是N! (N的阶乘)

因此

其时间复杂度为O(T)=N^2 *N!

空间复杂度:
O(T)=N^2

(这下是完全没问题啦!)
???

参考博客:

参考博客

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/128485.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 推荐一本适合初学者全面自学python的书(附赠电子书)

    推荐一本适合初学者全面自学python的书(附赠电子书)今天一个朋友问我:有个朋友要学习python,她属于那种特别能啃书的,让我推荐。我学python都是无师自通的,没有看过什么书,因此无法给她推荐,问我有什么意见?他那个朋友是零基础的,ctrl

  • 微信小程序抢票脚本怎么写_小程序抢票脚本

    微信小程序抢票脚本怎么写_小程序抢票脚本小程序抢票脚本@TOC微信小程序抢票脚本所使用的模块:request和re工具:pycharm和fiddler1.首先通过fiddler工具抓取到请求和参数选择场地信息url信息付款url信息2.代码部分,编写脚本选场地//选场地changdi_url=”https://sapb.szosc.cn/index.php/wxplace/place/pay”date={‘price’:’30’,’fieldtype’:”,

  • python表白代码简单「建议收藏」

    python表白代码简单「建议收藏」谢谢大家的支持,您的一键三连是罡罡同学前进的最大动力!一键三连一键三连一键三连一键三连一键三连一键三连python表白代码简单1.首先你要现有python,以及环境配置(自己去网上找资源)2.下载pycharm(相当于Dev、Eclipse编译器)3.复制粘贴即可下面放上源代码:importturtle#str=input(‘请输入表白语:’)str=”糖浆不分离”str1=”2020/12/22~2021/2/16″turtle.speed(

  • Android开发13——内容提供者ContentProvider的基本使用

    Android开发13——内容提供者ContentProvider的基本使用

  • cmd命令ping不是内部或外部命令_ping命令次数

    cmd命令ping不是内部或外部命令_ping命令次数介绍ping命令是一个用来测试能不能与另一台主机交换数据包的命令,通常我们会用ping命令测试域名可达性。1.语法:ping+ip(v4)或者域名实例一:通过ping百度域名,以此来看网络是否正常连接@echooffpingwww.baidu.com>nuliferrorlevel0(echo网络连接正常)elseecho网络连接异常pauseexit2.参数,可调出cmd窗口输入ping/?列出具体的参数介绍几个常用的参数:1.ping/t一直ping一

  • RPM卸载 (Linux 使用)[通俗易懂]

    RPM卸载 (Linux 使用)[通俗易懂]可以先用rpm-q’xxx’或者rpm-qf’xxx/bin/xxxx.xx’来查询一下所属的rpm包的名字。然后用rpm-e’xxxxxx’来删之。’xxx/bin/xxxx.xx’是一个包中任意的文件’xxxxxx’是查询得到的rpm包的名称rpm-e的时候后面的文件名不用加版本号详细说明:安全地卸载RPM卸载软件包,并不是简单地将原来安

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号