算法分析課程設(shè)計(jì)

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告書 評(píng)分：_題目：（例如）基于矩陣變換算法的圖同構(gòu)識(shí)別設(shè)計(jì)人：李文森一、 實(shí)驗(yàn)環(huán)境：1、硬件環(huán)境：個(gè)人機(jī)，CPU主頻：2.3GHZ 內(nèi)存：4GB2、軟件環(huán)境：操作系統(tǒng)：windows編程語(yǔ)言：C+二、 實(shí)驗(yàn)任務(wù)解決方案：實(shí)驗(yàn)思路：設(shè)兩個(gè)無(wú)向圖G=(V,E),G=(V,E),G,G同構(gòu)當(dāng)且僅當(dāng)兩圖的鄰接矩陣、行間同或矩陣、行間異或矩陣具有相同的行行置換。1. 矩陣算法步驟a. 根據(jù)定義，求出同型矩陣AAG、AAG.b. 計(jì)算出行間同或矩陣RAG、RAG，行間異或矩陣RXG、RXG.c. 以圖G=(V,E)的行間異或矩陣為參照，對(duì)RXG的每一行，從RXG搜索所有行，找到一個(gè)匹

2、配。若不存在相應(yīng)匹配，則兩圖不同構(gòu)；若匹配，轉(zhuǎn)步驟（4）.d. 判斷鄰接矩陣AG、AG,行間同或矩陣中是否存在同樣的匹配，若匹配存在，調(diào)整鄰接矩陣AG、行間異或矩陣RXG、行間同或矩陣RAG對(duì)應(yīng)的行和列；若不匹配，則不同構(gòu).2、基于矩陣變換算法的流程圖。3、基于矩陣變換算法實(shí)現(xiàn)的關(guā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;/核心代碼/異或矩陣行轉(zhuǎn)換void wensen_

3、hx(int *p1,int *p13,int *p14,int *p2,int *p23,int *p24,int n)int *p77=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p13int *p88=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p23int *p33=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p1int *p44=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p14int *p55=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p2int *p66=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p24int *p99=new intn;/用于行行替換

4、的臨時(shí)數(shù)組int t;int tt;/進(jìn)行跳轉(zhuǎn)判斷int ttt=0;/進(jìn)行跳轉(zhuǎn)判斷/行行替換for( int i=0;i<n;i+)/首先進(jìn)行行賦值給另外一個(gè)數(shù)組p13for(int i77=0;i77<n;i77+)p77i77=p13ii77;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組p1for(int i33=0;i33<n;i33+)p33i33=p1ii33;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組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);/開始進(jìn)行比較,p12的每一行與p23的每一行進(jìn)行比較for(int y=i;y<n;y+)tt=0;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組for(int i88=0;i88<n;i88+)p88i88=p23yi88;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組for(int i55=0;i55<n;i55+)p55i55=p2yi55;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組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)/也就是各個(gè)都相等,找到匹配/開始進(jìn)行鄰接矩陣對(duì)應(yīng)位置比較for(int b=0;b<n;b+)if(p33b=p55b)continue;else if(b<n-1)cout<<"不同構(gòu)n"return;/開始進(jìn)行同或矩陣for(int c=0;c<n;c+)if(p44c=p66c)continue;else if(c<n-1)cout<<"不同構(gòu)n"return;ttt+;/表

7、示成功匹配一行/進(jìn)行行行轉(zhuǎn)換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;/進(jìn)行行行轉(zhuǎn)換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;/進(jìn)行行行轉(zhuǎn)換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)/一直循環(huán)到最后都未找到匹配cout<<"不同構(gòu)n"return;elsebreak;/上面的匹配沒(méi)有問(wèn)題，則進(jìn)行行替換if(tt=n-1)if(ttt=n)cout<<"同構(gòu)n"return;else break;/成功跳出循環(huán)判斷下一行三、 基于矩陣變換算法的計(jì)算復(fù)雜度分析（最好、最

9、差、平均情況復(fù)雜度）：1.同構(gòu)最好情況是：每一行都互相對(duì)應(yīng)，所以復(fù)雜度為：3n2+3n3+8n2時(shí)間復(fù)雜度為O(n3)。2.同構(gòu)最壞情況是：每一行都與最后一行對(duì)應(yīng)，所以復(fù)雜度為：3n2+3n3+8n*n!時(shí)間復(fù)雜度為O(n*n!)3.所以平均時(shí)間復(fù)雜度為O(n*n!)四、 總結(jié)綜合實(shí)驗(yàn)心得體會(huì)：1.實(shí)例演示鄰接矩陣：2. 實(shí)驗(yàn)體會(huì)本課程設(shè)計(jì)是為了判斷無(wú)向圖是否同構(gòu)，采用了較為容易實(shí)現(xiàn)的鄰接矩陣，同時(shí)用到了同型矩陣、行間異或矩陣、行間同或矩陣等知識(shí)。知道了同構(gòu)當(dāng)且僅當(dāng)兩圖的鄰接矩陣、行間同或矩陣、行間異或矩陣具有相同的行行置換。通過(guò)他們之間對(duì)應(yīng)的關(guān)系，我寫出了這個(gè)算法，并已經(jīng)初步測(cè)試過(guò)，能正確判

10、斷圖是否同構(gòu)。通過(guò)本次的課程設(shè)計(jì)，讓我更好的了解了算法的重要性，一個(gè)優(yōu)異的算法能極大的減少運(yùn)行時(shí)間。在本課程設(shè)計(jì)上，在異或矩陣的比對(duì)上，為了更好的實(shí)現(xiàn)元素比對(duì)，我采用了了冒泡排序法，可以讓它實(shí)現(xiàn)有序的比對(duì)，這樣就減少了比對(duì)的次數(shù)，減少運(yùn)算時(shí)間。本算法還有挺多改進(jìn)的地方，例如，算法復(fù)雜度太大，所以算法還有待進(jìn)一步改善，以達(dá)到更優(yōu)。/完全代碼#include<iostream>using namespace std;/定義函數(shù)/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;/輸出函數(shù)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;/核心代碼/異或矩陣行轉(zhuǎn)換void we

14、nsen_hx(int *p1,int *p13,int *p14,int *p2,int *p23,int *p24,int n)int *p77=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p13int *p88=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p23int *p33=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p1int *p44=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p14int *p55=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p2int *p66=new intn;/用于替換的臨時(shí)一維數(shù)組，存放p24int *p99=new intn;/用

15、于行行替換的臨時(shí)數(shù)組int t;int tt;/進(jìn)行跳轉(zhuǎn)判斷int ttt=0;/進(jìn)行跳轉(zhuǎn)判斷/行行替換for( int i=0;i<n;i+)/首先進(jìn)行行賦值給另外一個(gè)數(shù)組p13for(int i77=0;i77<n;i77+)p77i77=p13ii77;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組p1for(int i33=0;i33<n;i33+)p33i33=p1ii33;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組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);/開始進(jìn)行比較,p12的每一行與p23的每一行進(jìn)行比較for(int y=i;y<n;y+)tt=0;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組for(int i88=0;i88<n;i88+)p88i88=p23yi88;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組for(int i55=0;i55<n;i55+)p55i55=p2yi55;/首先進(jìn)行行賦值給另外一個(gè)數(shù)組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)/也就是各個(gè)都相等,找到匹配/開始進(jìn)行鄰接矩陣對(duì)應(yīng)位置比較for(int b=0;b<n;b+)if(p33b=p55b)continue;else if(b<n-1)cout<<"不同構(gòu)n"return;/開始進(jìn)行同或矩陣for(int c=0;c<n;c+)if(p44c=p66c)continue;else if(c<n-1)cout<<"不同構(gòu)n"return;tt

18、t+;/表示成功匹配一行/進(jìn)行行行轉(zhuǎn)換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;/進(jìn)行行行轉(zhuǎn)換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;/進(jìn)行行行轉(zhuǎn)換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)/一直循環(huán)到最后都未找到匹配cout<<"不同構(gòu)n"return;elsebreak;/上面的匹配沒(méi)有問(wèn)題，則進(jìn)行行替換if(tt=n-1)if(ttt=n)cout<<"同構(gòu)n"return;else break;/成功跳出循環(huán)判斷下一行/主程序int main()int n

20、;/圖的頂點(diǎn)數(shù)char *s;/字符串提示char ss='y'cout<<"n"cout<<"*歡迎進(jìn)入李文森圖同構(gòu)判斷*nnn"while(ss='y') cout<<"請(qǐng)輸入圖的頂點(diǎn)個(gè)數(shù)n"cin>>n;/接收第一個(gè)圖的頂點(diǎn)個(gè)數(shù)if(cin.fail()cout<<"*輸入錯(cuò)誤，請(qǐng)重新輸入*n"continue;else/*創(chuàng)建數(shù)組/圖一鄰接矩陣數(shù)組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;/圖二鄰接矩陣數(shù)組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;/*/接收第一個(gè)鄰接矩陣的二維數(shù)組cout<<"請(qǐng)輸入第一個(gè)圖的鄰接矩陣n"for(int i11=0;i11<n;i11+)for(int j11=0;j11<n;j11+)cin>>p1i11j11;/接收第二個(gè)鄰接矩陣的二維數(shù)組cout<<"請(qǐng)輸入第二個(gè)圖的鄰接矩陣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