算法分析课程设计

1、算法分析与设计实验报告书 评分：_题目：（例如）基于矩阵变换算法的图同构识别设计人：李文森一、 实验环境：1、硬件环境：个人机，CPU主频：2.3GHZ 内存：4GB2、软件环境：操作系统：windows编程语言：C+二、 实验任务解决方案：实验思路：设两个无向图G=(V,E),G=(V,E),G,G同构当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换。1. 矩阵算法步骤a. 根据定义，求出同型矩阵AAG、AAG.b. 计算出行间同或矩阵RAG、RAG，行间异或矩阵RXG、RXG.c. 以图G=(V,E)的行间异或矩阵为参照，对RXG的每一行，从RXG搜索所有行，找到一个匹

2、配。若不存在相应匹配，则两图不同构；若匹配，转步骤（4）.d. 判断邻接矩阵AG、AG,行间同或矩阵中是否存在同样的匹配，若匹配存在，调整邻接矩阵AG、行间异或矩阵RXG、行间同或矩阵RAG对应的行和列；若不匹配，则不同构.2、基于矩阵变换算法的流程图。3、基于矩阵变换算法实现的关键代码。/*冒泡排序void wensen_mp(int mp,int n)int t;for(int i=0;i<n-1;i+)for(int j=0;j<n-1-i;j+)if(mpj>mpj+1)t=mpj;mpj=mpj+1;mpj+1=t;/核心代码/异或矩阵行转换void wensen_

3、hx(int *p1,int *p13,int *p14,int *p2,int *p23,int *p24,int n)int *p77=new intn;/用于替换的临时一维数组，存放p13int *p88=new intn;/用于替换的临时一维数组，存放p23int *p33=new intn;/用于替换的临时一维数组，存放p1int *p44=new intn;/用于替换的临时一维数组，存放p14int *p55=new intn;/用于替换的临时一维数组，存放p2int *p66=new intn;/用于替换的临时一维数组，存放p24int *p99=new intn;/用于行行替换

4、的临时数组int t;int tt;/进行跳转判断int ttt=0;/进行跳转判断/行行替换for( int i=0;i<n;i+)/首先进行行赋值给另外一个数组p13for(int i77=0;i77<n;i77+)p77i77=p13ii77;/首先进行行赋值给另外一个数组p1for(int i33=0;i33<n;i33+)p33i33=p1ii33;/首先进行行赋值给另外一个数组for(int i44=0;i44<n;i44+)p44i44=p14ii44;/p77,p33,p44冒泡排序wensen_mp(p77,n);wensen_mp(p33,n);we

5、nsen_mp(p44,n);/开始进行比较,p12的每一行与p23的每一行进行比较for(int y=i;y<n;y+)tt=0;/首先进行行赋值给另外一个数组for(int i88=0;i88<n;i88+)p88i88=p23yi88;/首先进行行赋值给另外一个数组for(int i55=0;i55<n;i55+)p55i55=p2yi55;/首先进行行赋值给另外一个数组for(int i66=0;i66<n;i66+)p66i66=p24yi66;/p88,p55,p66冒泡排序wensen_mp(p88,n);wensen_mp(p55,n);wensen_m

6、p(p66,n);/开始比较for(int a=0;a<n;a+)if(p77a=p88a)tt=a;if(a=n-1)/也就是各个都相等,找到匹配/开始进行邻接矩阵对应位置比较for(int b=0;b<n;b+)if(p33b=p55b)continue;else if(b<n-1)cout<<"不同构n"return;/开始进行同或矩阵for(int c=0;c<n;c+)if(p44c=p66c)continue;else if(c<n-1)cout<<"不同构n"return;ttt+;/表

7、示成功匹配一行/进行行行转换p2for(int u1=0;u1<n;u1+)t=p2iu1;p2iu1=p2yu1;p2yu1=t;for(int u11=0;u11<n;u11+)t=p2u11i;p2u11i=p2u11y;p2u11y=t;/进行行行转换p23for(int u2=0;u2<n;u2+)t=p23iu2;p23iu2=p23yu2;p23yu2=t;for(int u22=0;u22<n;u22+)t=p23u22i;p23u22i=p23u22y;p23u22y=t;/进行行行转换p24for(int u3=0;u3<n;u3+)t=p24

8、iu3;p24iu3=p24yu3;p24yu3=t;for(int u33=0;u33<n;u33+)t=p24u33i;p24u33i=p24u33y;p24u33y=t;break;elsecontinue;else if(y=n-1)/一直循环到最后都未找到匹配cout<<"不同构n"return;elsebreak;/上面的匹配没有问题，则进行行替换if(tt=n-1)if(ttt=n)cout<<"同构n"return;else break;/成功跳出循环判断下一行三、 基于矩阵变换算法的计算复杂度分析（最好、最

9、差、平均情况复杂度）：1.同构最好情况是：每一行都互相对应，所以复杂度为：3n2+3n3+8n2时间复杂度为O(n3)。2.同构最坏情况是：每一行都与最后一行对应，所以复杂度为：3n2+3n3+8n*n!时间复杂度为O(n*n!)3.所以平均时间复杂度为O(n*n!)四、 总结综合实验心得体会：1.实例演示邻接矩阵：2. 实验体会本课程设计是为了判断无向图是否同构，采用了较为容易实现的邻接矩阵，同时用到了同型矩阵、行间异或矩阵、行间同或矩阵等知识。知道了同构当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换。通过他们之间对应的关系，我写出了这个算法，并已经初步测试过，能正确判

10、断图是否同构。通过本次的课程设计，让我更好的了解了算法的重要性，一个优异的算法能极大的减少运行时间。在本课程设计上，在异或矩阵的比对上，为了更好的实现元素比对，我采用了了冒泡排序法，可以让它实现有序的比对，这样就减少了比对的次数，减少运算时间。本算法还有挺多改进的地方，例如，算法复杂度太大，所以算法还有待进一步改善，以达到更优。/完全代码#include<iostream>using namespace std;/定义函数/22222222222222222222222同型矩阵void wensen_tx(int *p1,int *p2,int n)for(int i=0;i<

11、;n;i+)for(int j=0;j<n;j+)if(p1ij>0)p2ij=1;elsep2ij=0;/3333333333333333333333异或矩阵void wensen_yh(int *p1,int *p2,int *p3,int n)for( int i=0;i<n;i+)for(int j=0;j<n;j+)if(i=j)p3ij=p1ii;elseint sum1,sum12;sum1=0;for(int k=0;k<n;k+)if(p2ik=p2jk)sum12=0;elsesum12=1;sum1=sum1+(p1ik+p1jk)*sum1

12、2;p3ij=sum1;/44444444444444444同或矩阵void wensen_th(int *p1,int *p2,int *p4,int n)for(int i=0;i<n;i+)for(int j=0;j<n;j+)if(i=j)p4ij=p1ii;elseint sum1,sum12;sum1=0;for(int k=0;k<n;k+)if(p2ik=p2jk)sum12=1;elsesum12=0;sum1=sum1+(p1ik+p1jk)*sum12;p4ij=sum1;/输出函数void wensen_out(int *p,char *s,int n

13、)cout<<s;cout<<"n"for(int i=0;i<n;i+)for(int j=0;j<n;j+)cout<<pij;cout<<"t"cout<<"n"/*冒泡排序void wensen_mp(int mp,int n)int t;for(int i=0;i<n-1;i+)for(int j=0;j<n-1-i;j+)if(mpj>mpj+1)t=mpj;mpj=mpj+1;mpj+1=t;/核心代码/异或矩阵行转换void we

14、nsen_hx(int *p1,int *p13,int *p14,int *p2,int *p23,int *p24,int n)int *p77=new intn;/用于替换的临时一维数组，存放p13int *p88=new intn;/用于替换的临时一维数组，存放p23int *p33=new intn;/用于替换的临时一维数组，存放p1int *p44=new intn;/用于替换的临时一维数组，存放p14int *p55=new intn;/用于替换的临时一维数组，存放p2int *p66=new intn;/用于替换的临时一维数组，存放p24int *p99=new intn;/用

15、于行行替换的临时数组int t;int tt;/进行跳转判断int ttt=0;/进行跳转判断/行行替换for( int i=0;i<n;i+)/首先进行行赋值给另外一个数组p13for(int i77=0;i77<n;i77+)p77i77=p13ii77;/首先进行行赋值给另外一个数组p1for(int i33=0;i33<n;i33+)p33i33=p1ii33;/首先进行行赋值给另外一个数组for(int i44=0;i44<n;i44+)p44i44=p14ii44;/p77,p33,p44冒泡排序wensen_mp(p77,n);wensen_mp(p33,

16、n);wensen_mp(p44,n);/开始进行比较,p12的每一行与p23的每一行进行比较for(int y=i;y<n;y+)tt=0;/首先进行行赋值给另外一个数组for(int i88=0;i88<n;i88+)p88i88=p23yi88;/首先进行行赋值给另外一个数组for(int i55=0;i55<n;i55+)p55i55=p2yi55;/首先进行行赋值给另外一个数组for(int i66=0;i66<n;i66+)p66i66=p24yi66;/p88,p55,p66冒泡排序wensen_mp(p88,n);wensen_mp(p55,n);wen

17、sen_mp(p66,n);/开始比较for(int a=0;a<n;a+)if(p77a=p88a)tt=a;if(a=n-1)/也就是各个都相等,找到匹配/开始进行邻接矩阵对应位置比较for(int b=0;b<n;b+)if(p33b=p55b)continue;else if(b<n-1)cout<<"不同构n"return;/开始进行同或矩阵for(int c=0;c<n;c+)if(p44c=p66c)continue;else if(c<n-1)cout<<"不同构n"return;tt

18、t+;/表示成功匹配一行/进行行行转换p2for(int u1=0;u1<n;u1+)t=p2iu1;p2iu1=p2yu1;p2yu1=t;for(int u11=0;u11<n;u11+)t=p2u11i;p2u11i=p2u11y;p2u11y=t;/进行行行转换p23for(int u2=0;u2<n;u2+)t=p23iu2;p23iu2=p23yu2;p23yu2=t;for(int u22=0;u22<n;u22+)t=p23u22i;p23u22i=p23u22y;p23u22y=t;/进行行行转换p24for(int u3=0;u3<n;u3+)

19、t=p24iu3;p24iu3=p24yu3;p24yu3=t;for(int u33=0;u33<n;u33+)t=p24u33i;p24u33i=p24u33y;p24u33y=t;break;elsecontinue;else if(y=n-1)/一直循环到最后都未找到匹配cout<<"不同构n"return;elsebreak;/上面的匹配没有问题，则进行行替换if(tt=n-1)if(ttt=n)cout<<"同构n"return;else break;/成功跳出循环判断下一行/主程序int main()int n

20、;/图的顶点数char *s;/字符串提示char ss='y'cout<<"n"cout<<"*欢迎进入李文森图同构判断*nnn"while(ss='y') cout<<"请输入图的顶点个数n"cin>>n;/接收第一个图的顶点个数if(cin.fail()cout<<"*输入错误，请重新输入*n"continue;else/*创建数组/图一邻接矩阵数组int *p1=new int*n;for(int i1=0;i1&l

21、t;n;i1+)p1i1=new intn;/图一同型矩阵int *p12=new int*n;for(i1=0;i1<n;i1+)p12i1=new intn;/图一行异或矩阵int *p13=new int*n;for(i1=0;i1<n;i1+)p13i1=new intn;/图一行同或矩阵int *p14=new int*n;for(i1=0;i1<n;i1+)p14i1=new intn;/图二邻接矩阵数组int *p2=new int*n;for(int i2=0;i2<n;i2+)p2i2=new intn;/图二同型矩阵int *p22=new int*

22、n;for(i1=0;i1<n;i1+)p22i1=new intn;/图二行异或矩阵int *p23=new int*n;for(i1=0;i1<n;i1+)p23i1=new intn;/图二行同或矩阵int *p24=new int*n;for(i1=0;i1<n;i1+)p24i1=new intn;/*/接收第一个邻接矩阵的二维数组cout<<"请输入第一个图的邻接矩阵n"for(int i11=0;i11<n;i11+)for(int j11=0;j11<n;j11+)cin>>p1i11j11;/接收第二个邻接矩阵的二维数组cout<<"请输入第二个图的邻接矩阵n"for(int i22=0;i22<n;i22+)for(int j22=0;j22<n;j22+)cin>>p2i22j22;/*/图一同型矩阵wensen_tx(p1,p12,n);/图一异或矩阵wensen_yh(p1,p12,p13,n);/图一同或矩阵wensen_th(p1