1.深度优先搜索
下面是深度优先搜索遍历的一个例子，我们用整数标记节点，G记录有向边，G[u][v]表示节点u指向节点v。用数组c[M]记录遍历状态：
c[u]==-1----表示u被dfs调用，但还没有返回
c[u]==0----表示从来没有遍历过
c[u]==1----表示已经遍历并返回
#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;//说明有环
if(c[v]==0 && !dfs(v) ) return false;//如果c[v]是0，则遍历v，此时如果子图有环，则停止遍历，返回false
}
std::cout<<u<<std::endl;
c[u]=1;
return true;
}
从注释也容易看出来了，深度优先搜索可以用来判断一个图是否有环。另外，深度优先搜索的顺序，恰恰满足拓扑排序
2.欧拉回路
2.1.无向图
我们把和一个点相连的边数是这个点的度数，因为一条边对应于两个点，因此，所有点的度数之和肯定是偶数。
一笔画的充要条件是：除了起点和终点外，其它点的度数一定是偶数。
2.2.有向图
对于有向图，除了起点终点外，入度等于出度，并且，起点的出度比入度大1，终点的入度比出度大1.
3.子集生成
我们把问题简化：假设集合有n个元素，是从1到n的整数。
3.1.增量构造法
A表示集合数组，n是集合数组内元素的个数，cur表示子集中元素的数目，当然，cur==0表示空集，此外，我们还假设，最开始的时候，A已经排好了序。
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.位向量法
对于每一个元素，用一个位表示它是否在子集中
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.二进制法
位向量法就是一种二进制法，此外，集合的并，交，差等运算，是可以转化成二进制运算的，所以。。。
4.回溯法
回溯法在递归构造中，把生成和检查结合起来，有效减少不必要的枚举。
举例：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.广度优先搜索
比如二叉树层次遍历，就是广度优先搜索的一个例子。我们用一个先进先出的队列，实现了树的广度优先搜索
对于图，仍然是要用队列来实现广度优先搜索，然而，图的情况稍微复杂，除了采用队列外，还应该引入另外的数据结构，来防止节点被重复遍历到。
举例：八数码问题
其实八数码问题可以归结为路径寻找问题，把每个状态看做一个节点，移动空格相邻的滑块，到达另一个节点，因此每种移动方式可以看做是一条边。
因为是图，因此需要特定的数据结构记录那些节点被遍历过了，如果考虑用一个数来表示，比如序列123456780就用123456780表示，这将耗费9^9这么多的空间，如果采用int型存储，这将是几百M的空间，显然这是不合理的。实际上，节点总数只有9！=362880，只有几M的空间，因此，我们需要一种编码方式，使得每个状态，和0到362880之间的整数一一对应，一种方式就是按字典序映射，下面的代码实现了这个功能：
#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;
}
利用上面编码规则，对八数码问题的解决办法：
/*
这个代码调试的也让人累觉不爱了。。。
1.memcpy函数按字节数拷贝内存，所以，是9*sizeof(int), 而不是9！！！
2.突然冒出个想法：不必要对d进行pop_front操作，把迭代器向前移动就可以了，然而。。。当插入或删除vector内的元素的时候，面临这迭代器失效问题。。。囧。。。
3.为了避免死循环，father对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结构来记录哪些被搜索过了。我们知道，map采用树的结构存储的。查找，插入等时间复杂度是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
*/
网友评论