图的同构识别算法——C++代码实现

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

阅读文章前需要知道一个概念:
邻接矩阵中的结点的次序是有实际意义的，当结点进行行变换的时候，必须对其对应的列也进行变换

实现代码和说明:

#include
#include
#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>>B.points;
    
    //判断第一个必要条件
    
	if(A.points!=B.points){
        cout<<"阶数不同！不同构！"<A.Matrix[i][j];
            if(A.Matrix[i][j]==1){
                A.edges++;
            }   
        }
    }
    
    cout<<"请输入第2个图的邻接矩阵："<>B.Matrix[i][j];
            if(B.Matrix[i][j]==1){
                B.edges++;
            }   
        }
    }
    
    //判断第二个必要条件
    
	
	if(A.edges!=B.edges){
        cout<<"边的条数不同！不同构！"<举例:
 图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 
③:判定函数Judge():
 
 bool Judge(){
 	for(i =0; i  
④交换行中度相同的函数并且行交换后列也交换，在交换前判定，交换完毕判定的函数SwapColumnsAndRowsAndJudge():
 
 bool SwapColumnsAndRowsAndJudge(){//直接根据点的度相同，进行列交换 每次交换完行列，都要进行判定：两个矩阵是否相同 
 	for(int x=0;x 
⑤新增加的两个行列置换函数(直接换)
 SwapRowsTwo():
 
bool SwapRowsTwo(int i,int j){//改进代码 
    int k;
    
    for(k=0;k 
⑥SwapColumnsTwo():
 
SwapColumnsTwo(int i,int j){//改进代码 
    int k;
    for(k=0;k 
完整代码如下:
 
#include
#include
#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>>B.points;
    C.points=A.points;//注意这里要初始化 
    //判断第一个必要条件
    
	if(A.points!=B.points){
        cout<<"阶数不同！不同构！"<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个图的邻接矩阵："<>B.Matrix[i][j];
            if(B.Matrix[i][j]==1){
                B.edges++;
            }   
        }
    }
    
    //判断第二个必要条件
    
	
	if(A.edges!=B.edges){
        cout<<"边的条数不同！不同构！"<测试图
 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 由于外面还有两层for循环,因此这里的时间复杂度为 O(T8)=N^4
 
 

 
 
O(T9)=N*N^2=N ^3
 因此其时间复杂度为:
 O(T)=O(T1)+……+O(T9)=N^4
 空间复杂度:
 O(T)=N^2
 
参考博客: 
参考博客
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5610402.html