1.深度優(yōu)先搜索
下面是深度優(yōu)先搜索遍歷的一個(gè)例子，我們用整數(shù)標(biāo)記節(jié)點(diǎn)，G記錄有向邊，G[u][v]表示節(jié)點(diǎn)u指向節(jié)點(diǎn)v。用數(shù)組c[M]記錄遍歷狀態(tài)：
c[u]==-1----表示u被dfs調(diào)用，但還沒(méi)有返回
c[u]==0----表示從來(lái)沒(méi)有遍歷過(guò)
c[u]==1----表示已經(jīng)遍歷并返回
#include <iostream>
#define M 100
int c[M];
int G[M][M];
bool dfs(int u){
c[u]=-1;
for(int v=0; v<M ; ++v)
if(G[u][v]){
if(c[v]==-1) return false;//說(shuō)明有環(huán)
if(c[v]==0 && !dfs(v) ) return false;//如果c[v]是0，則遍歷v，此時(shí)如果子圖有環(huán)，則停止遍歷，返回false
}
std::cout<<u<<std::endl;
c[u]=1;
return true;
}
從注釋也容易看出來(lái)了，深度優(yōu)先搜索可以用來(lái)判斷一個(gè)圖是否有環(huán)。另外，深度優(yōu)先搜索的順序，恰恰滿足拓?fù)渑判?/p>
2.歐拉回路
2.1.無(wú)向圖
我們把和一個(gè)點(diǎn)相連的邊數(shù)是這個(gè)點(diǎn)的度數(shù)，因?yàn)橐粭l邊對(duì)應(yīng)于兩個(gè)點(diǎn)，因此，所有點(diǎn)的度數(shù)之和肯定是偶數(shù)。
一筆畫的充要條件是：除了起點(diǎn)和終點(diǎn)外，其它點(diǎn)的度數(shù)一定是偶數(shù)。
2.2.有向圖
對(duì)于有向圖，除了起點(diǎn)終點(diǎn)外，入度等于出度，并且，起點(diǎn)的出度比入度大1，終點(diǎn)的入度比出度大1.
3.子集生成
我們把問(wèn)題簡(jiǎn)化：假設(shè)集合有n個(gè)元素，是從1到n的整數(shù)。
3.1.增量構(gòu)造法
A表示集合數(shù)組，n是集合數(shù)組內(nèi)元素的個(gè)數(shù)，cur表示子集中元素的數(shù)目，當(dāng)然，cur==0表示空集，此外，我們還假設(shè)，最開始的時(shí)候，A已經(jīng)排好了序。
void print_sub_set(int A[], int n, int cur){
for(int i=0 ; i<cur; ++i)
std::cout<<A[i]<<" "<<std::flush;
std::cout<<std::endl;
int s=cur?A[cur-1]:0;
for(int i=s ; i<n ; i++){
A[cur]=i+1;
print_sub_set(A ,n, cur+1);
}
}
3.2.位向量法
對(duì)于每一個(gè)元素，用一個(gè)位表示它是否在子集中
void bit_vector(int B[], int n , int cur){
if(cur==n){
for(int i=0 ; i<n ; ++i)
if(B[i])
std::cout<<i+1<<std::flush;
std::cout<<std::endl;
return;
}
B[cur]=1;
bit_vector(B, n, cur+1);
B[cur]=0;
bit_vector(B, n, cur+1);
}
3.3.二進(jìn)制法
位向量法就是一種二進(jìn)制法，此外，集合的并，交，差等運(yùn)算，是可以轉(zhuǎn)化成二進(jìn)制運(yùn)算的，所以。。。
4.回溯法
回溯法在遞歸構(gòu)造中，把生成和檢查結(jié)合起來(lái)，有效減少不必要的枚舉。
舉例：n皇后問(wèn)題
void queen_(int *A , int n, int cur , int *tot){
if(cur==n) ++(*tot);
else for(int i=0; i<n ;++i){
A[cur]=i;
bool ok=true;
for(int j=0; j<cur ; ++j)
if(A[j]==A[cur] || A[j]+j==A[cur]+cur || A[j]-j==A[cur]-cur) ok=false;
if(ok) queen_(A, n, cur+1, tot);
}
}
int queen(int n){
int *A=new int[n];
int tot=0;
queen_(A, n , 0 , &tot);
delete[] A;
return tot;
}
5.廣度優(yōu)先搜索
比如二叉樹層次遍歷，就是廣度優(yōu)先搜索的一個(gè)例子。我們用一個(gè)先進(jìn)先出的隊(duì)列，實(shí)現(xiàn)了樹的廣度優(yōu)先搜索
對(duì)于圖，仍然是要用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先搜索，然而，圖的情況稍微復(fù)雜，除了采用隊(duì)列外，還應(yīng)該引入另外的數(shù)據(jù)結(jié)構(gòu)，來(lái)防止節(jié)點(diǎn)被重復(fù)遍歷到。
舉例：八數(shù)碼問(wèn)題
其實(shí)八數(shù)碼問(wèn)題可以歸結(jié)為路徑尋找問(wèn)題，把每個(gè)狀態(tài)看做一個(gè)節(jié)點(diǎn)，移動(dòng)空格相鄰的滑塊，到達(dá)另一個(gè)節(jié)點(diǎn)，因此每種移動(dòng)方式可以看做是一條邊。
因?yàn)槭菆D，因此需要特定的數(shù)據(jù)結(jié)構(gòu)記錄那些節(jié)點(diǎn)被遍歷過(guò)了，如果考慮用一個(gè)數(shù)來(lái)表示，比如序列123456780就用123456780表示，這將耗費(fèi)9^9這么多的空間，如果采用int型存儲(chǔ)，這將是幾百M(fèi)的空間，顯然這是不合理的。實(shí)際上，節(jié)點(diǎn)總數(shù)只有9！=362880，只有幾M的空間，因此，我們需要一種編碼方式，使得每個(gè)狀態(tài)，和0到362880之間的整數(shù)一一對(duì)應(yīng)，一種方式就是按字典序映射，下面的代碼實(shí)現(xiàn)了這個(gè)功能：
#include <iostream>
int encode(int *A, int n){
if(A==NULL || n<1)
return -1;
if(n==1)
return 0;
int *table=new int[n];
table[0]=1;
for(int i=1 ; i< n ; ++i)
table[i]=table[i-1]*i;
int *exist=new int[n];
for(int i=0 ; i<n ; ++i)
exist[i]=0;
int sum=0;
for(int i=0; i<n-1 ; ++i ){
int temp=A[i];
exist[temp]=1;
for(int j=0 ; j<A[i] ;++j)
if(exist[j])
--temp;
sum+=temp*table[n-1-i];
}
delete[] table;
delete[] exist;
return sum;
}
int decode(int A[], int n, int code){
if(A==NULL || n<1 || code<0)
return 0;
int *table=new int[n+1];
table[0]=1;
for(int i=1 ; i< n+1 ; ++i)
table[i]=table[i-1]*i;
if(code >=table[n])
return -1;
int *exist=new int[n];
for(int i=0 ; i<n ; ++i)
exist[i]=0;
int rank;
for(int i=0; i<n ; ++i){
int val;
rank=code/table[n-1-i];
for(int j=0 ; j<n ; ++j){
if(!exist[j])
--rank;
if(rank<0){
val=j;
break;
}
}
A[i]=val;
exist[val]=1;
code=code%table[n-1-i];
}
return 1;
}
/********test***************/
void print(int *A, int n){
for(int i=0; i<n ; ++i)
std::cout<<A[i]<<" "<<std::flush;
std::cout<<std::endl;
}
int main(){
int n;
while(std::cin>>n){
if(n<=0)
break;
int *A=new int[n];
int code=0;
int term=1;
while(term==1){
term=decode(A, n, code);
if(term != 1)
break;
int t=encode(A, n);
if(code != t){
std::cout<<"wrong !"<<std::endl;
std::cout<<"A:"<<std::endl;
print(A, n);
std::cout<<"code: "<<code<<std::endl;
std::cout<<"encode: "<<t<<std::endl;
break;
}
++code;
}
std::cout<<"code: "<<code<<std::endl;
delete[] A;
}
return 0;
}
利用上面編碼規(guī)則，對(duì)八數(shù)碼問(wèn)題的解決辦法：
/*
這個(gè)代碼調(diào)試的也讓人累覺不愛了。。。
1.memcpy函數(shù)按字節(jié)數(shù)拷貝內(nèi)存，所以，是9*sizeof(int), 而不是9！?。?2.突然冒出個(gè)想法：不必要對(duì)d進(jìn)行pop_front操作，把迭代器向前移動(dòng)就可以了，然而。。。當(dāng)插入或刪除vector內(nèi)的元素的時(shí)候，面臨這迭代器失效問(wèn)題。。。囧。。。
3.為了避免死循環(huán)，father對(duì)start也要有記錄
*/
#include <iostream>
#include <vector>
#include <cstring>
int encode(int *A, int n){
if(A==NULL || n<1)
return -1;
if(n==1)
return 0;
int *table=new int[n];
table[0]=1;
for(int i=1 ; i< n ; ++i)
table[i]=table[i-1]*i;
int *exist=new int[n];
for(int i=0 ; i<n ; ++i)
exist[i]=0;
int sum=0;
for(int i=0; i<n-1 ; ++i ){
int temp=A[i];
exist[temp]=1;
for(int j=0 ; j<A[i] ;++j)
if(exist[j])
--temp;
sum+=temp*table[n-1-i];
}
delete[] table;
delete[] exist;
return sum;
}
int decode(int A[], int n, int code){
if(A==NULL || n<1 || code<0)
return 0;
int *table=new int[n+1];
table[0]=1;
for(int i=1 ; i< n+1 ; ++i)
table[i]=table[i-1]*i;
if(code >=table[n])
return -1;
int *exist=new int[n];
for(int i=0 ; i<n ; ++i)
exist[i]=0;
int rank;
for(int i=0; i<n ; ++i){
int val;
rank=code/table[n-1-i];
for(int j=0 ; j<n ; ++j){
if(!exist[j])
--rank;
if(rank<0){
val=j;
break;
}
}
A[i]=val;
exist[val]=1;
code=code%table[n-1-i];
}
return 1;
}
int main(){
std::vector<int> father(362880);
std::vector<int> dist(362880);
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
int goon;
std::cout<<"go on ??"<<std::endl;
while (std::cin>>goon) {
if(goon==0)
break;
int *star=new int[9];
int *dest=new int[9];
std::cout<<"input start:"<<std::endl;
for(int i=0 ; i<9 ; ++i)
std::cin>>star[i];
std::cout<<"input dest:"<<std::endl;
for(int i=0; i<9 ; ++i)
std::cin>>dest[i];
for(auto &s:father)
s=-1;
std::vector<int> d;
int estar=encode(star, 9);
int edest=encode(dest, 9);
d.push_back(estar);
dist[d[0]]=0;
father[d[0]]=d[0];
int front=0;
while(front != d.size()){
int cur=d[front];
int S[9];
decode(S, 9, cur);
int z;
for(z=0; z < 9 ; ++z)
if(S[z]==0)
break;
int row=z/3;
int col=z%3;
bool ok=false;
for(int di=0; di<4 ; ++di){
int nrow=row+dx[di];
int ncol=col+dy[di];
if(nrow>=0 && nrow<3 && ncol>=0 && ncol<3){
int nz=nrow*3+ncol;
int nS[9];
std::memcpy(&nS[0], &S[0], 9*sizeof(int));
nS[z]=nS[nz];
nS[nz]=0;
int enS=encode(nS, 9);
if(father[enS] == -1){
father[enS]=cur;
dist[enS]=dist[cur]+1;
if(enS==edest){
ok=true;
break;
}
d.push_back(enS);
}
}
}
if(ok)
break;
++front;
}
std::cout<<"shortest: "<<dist[edest]<<std::endl;
delete[] star;
delete[] dest;
std::cout<<"go on ??"<<std::endl;
}
return 0;
}
/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/
也可以用map結(jié)構(gòu)來(lái)記錄哪些被搜索過(guò)了。我們知道，map采用樹的結(jié)構(gòu)存儲(chǔ)的。查找，插入等時(shí)間復(fù)雜度是O(logn)，因此比前面的方法慢些。為了便于討論，我們省去了father，只用dist記錄:
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
int encode(int A[], int n){
int sum=0;
for(int i=0; i< n ; ++i)
sum=sum*10+A[i];
return sum;
}
void decode(int A[], int n , int code){
for(int i=n-1; i>=0 ; --i){
A[i]=code%10;
code/=10;
}
}
int main(){
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
int goon;
std::cout<<"go on ??"<<std::endl;
while (std::cin>>goon) {
if(goon==0)
break;
int *star=new int[9];
int *dest=new int[9];
std::cout<<"input start:"<<std::endl;
for(int i=0 ; i<9 ; ++i)
std::cin>>star[i];
std::cout<<"input dest:"<<std::endl;
for(int i=0; i<9 ; ++i)
std::cin>>dest[i];
std::map<int, int> dist;
std::vector<int> d;
int en_star=encode(star, 9);
int en_dest=encode(dest, 9);
d.push_back(en_star);
dist[en_star]=0;
int front=0;
while(front != d.size()){
int cur=d[front];
int S[9];
decode(S, 9, cur);
int z;
for(z=0; z<9 ; ++z)
if(S[z]==0)
break;
int row = z/3;
int col = z%3;
bool ok=false;
for(int i=0; i<4 ; ++i){
int nrow=row+dx[i];
int ncol=col+dy[i];
if(nrow>=0 && nrow<3 && ncol>=0 && ncol<3){
int nz=nrow*3+ncol;
int nS[9];
memcpy(nS, S, 9*sizeof(int));
nS[z]=nS[nz];
nS[nz]=0;
int enS=encode(nS, 9);
if(dist.find(enS) == dist.end()){
dist[enS]=dist[cur]+1;
if(enS==en_dest){
ok=true;
break;
}
d.push_back(enS);
}
}
}
if(ok)
break;
++front;
}
if(dist.find(en_dest) != dist.end())
std::cout<<"shortest steps: "<<dist[en_dest]<<std::endl;
else
std::cout<<"do not exist ! ! ! "<<std::endl;
delete[] star;
delete[] dest;
std::cout<<"go on ??"<<std::endl;
}
return 0;
}
/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/
