算法分析课程设计.doc

《算法分析课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告书评分：____________题目：（例如）基于矩阵变换算法的图同构识别设计人：李文森班级：网络工程2班学号：1214080613213一、实验环境：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

2、=(V,E)的行间异或矩阵为参照，对RXG的每一行，从RXG’搜索所有行，找到一个匹配。若不存在相应匹配，则两图不同构；若匹配，转步骤（4）.d.判断邻接矩阵AG、AG’,行间同或矩阵中是否存在同样的匹配，若匹配存在，调整邻接矩阵AG’、行间异或矩阵RXG’、行间同或矩阵RAG’对应的行和列；若不匹配，则不同构.2、基于矩阵变换算法的流程图。3、基于矩阵变换算法实现的关键代码。//*********************************冒泡排序voidwensen_mp(intmp[],intn){intt;for(inti=0;i

3、jmp[j+1]){t=mp[j];mp[j]=mp[j+1];mp[j+1]=t;}}}}/////////////////////////核心代码//异或矩阵行转换voidwensen_hx(int**p1,int**p13,int**p14,int**p2,int**p23,int**p24,intn){int*p77=newint[n];//用于替换的临时一维数组，存放p13int*p88=newint[n];//用于替换的临时一维数组，存放p23int*p33=newint[n];//用于替换的临时一维数组，存放p1int*p44=

4、newint[n];//用于替换的临时一维数组，存放p14int*p55=newint[n];//用于替换的临时一维数组，存放p2int*p66=newint[n];//用于替换的临时一维数组，存放p24int*p99=newint[n];//用于行行替换的临时数组intt;inttt;//进行跳转判断intttt=0;//进行跳转判断//行行替换for(inti=0;i

5、3

6、数组for(inti55=0;i55

7、(p33[b]==p55[b]){continue;}elseif(b