一、图搜索概论
树的定义：
树 (Tree) 是 n (n≥0) 个结点的有限集。若 n = 0，称
为空树；若 n > 0，则它满足如下两个条件：
(1) 有且仅有一个特定的称为根 (Root) 的结点；
(2) 其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2,
T3, …, Tm，其中每一个集合本身又是一棵树，并称为
根的子树 (SubTree)。
基本术语：
根节点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数，度=0就是叶子即终端结点
森林：是由m棵互不相交的树的集合，把根结点删除了就是森林。一颗树可以看做是一个特殊的森林。树一定是森林，森林不一定是树。
图的定义：
图 (Graph) 是一种复杂的非线性数据结构，由顶
点集合及顶点间的关系(也称弧或边)集合组成。可
以表示为： G＝(V, {VR})
图的基本术语：
有向图和无向图
完全图：有n(n-1)/2条边的无向图
完全有向图：有n(n-1)条边的有向图
入度：有向图中以顶点v为终点的弧目称为v的入度
初度：有向图中以顶点v为起始的弧目称为v的出度
图的存储结构之数组表示法：
图的存储结构之邻接表
二叉树的遍历：三种
根左右：先（根）序遍历
左根右：中（根）序遍历
左右根：后（根）序遍历
图的搜索：
显示图的穷举搜索：广度与深度
隐式图的穷举搜索：回溯与分支
二、PPT例题
1.八（六）皇后问题：
有六位皇后，在一个6x6的表格中，有六个皇后，为了让他们不互相攻击（不在同一行同一列同一斜方向），请给她们安排位置。
经典八皇后问题，关键点在于限制条件：不在一个列，不在一个斜线，
不在一个列用checklie[j]=0;然而不在一个斜线则发现行号x与列号j之间的关系：
x+j与x-j+6是固定值即：checkxie[x+j]=0;向右上斜checkxie2[x-j+6]=0;向左上斜
#include<bits/stdc++.h>
using namespace std;
int checklie[100]={0};//判断当前列有没有用过
int checkxie[100]={0};//判断右上和左下的那条斜线有没有用过
int checkxie2[100]={0};//判断左上和右下的那条斜线有没有用过
int total=0;//记录结果数
void dfs(int x){ //x当前行数
if(x==7){//当前x=7是结束，结果加一
total++;
return;
}
for(int i=1;i<=6;i++){
if(checklie[i]==0&&checkxie[x+i]==0&&checkxie2[x-i+6]==0){//判断
checklie[i]=1;
checkxie[x+i]=1;
checkxie2[x-i+6]=1;
dfs(x+1);//继续深搜下一行
checklie[i]=0;//回溯
checkxie[x+i]=0;
checkxie2[x-i+6]=0;
}
}
}
int main(){
dfs(1);
cout<<total;
}
2.走迷宫问题
题目：如下一个地图，其中标记为0的部分可以行走，但是标记为1的部分不能走，问需要到达终点（标记为2）的最短路程是多少？
0,0,0,0,0,1,
0,0,0,0,1,0,
1,0,0,0,1,1,
0,1,0,0,0,0,
0,1,0,1,0,0,
0,0,0,0,0,2
使用广度优先遍历办法
#include<bits/stdc++.h>
using namespace std;
int mape[6][6]={//题目要求地图
0,0,0,0,0,1,
0,0,0,0,1,0,
1,0,0,0,1,1,
0,1,0,0,0,0,
0,1,0,1,0,0,
0,0,0,0,0,2
};
int x[4]={0,1,0,-1};//左右走向
int y[4]={1,0,-1,0};//上下走向
int check[10][10]={0};//检查是否走过
struct aa{
int xx;
int yy;
int s;
}a[100]; //用结构体实现广度探索
int main(){
int tx=0;
int ty=0;
int head=1;
int tail=1;
a[tail].xx=tx;
a[tail].yy=ty;
a[tail].s=0;
tail++;
check[0][0]=1;
int fage=0;
while(head<tail){
for(int i=0;i<4;i++){
tx=a[head].xx+x[i];
ty=a[head].yy+y[i];
if(ty<0||ty>6||tx<0||tx>6){//越界检查
continue;
}
if(check[tx][ty]==0&&mape[tx][ty]!=1){
a[tail].xx=tx;
a[tail].yy=ty;
a[tail].s=a[head].s+1;
check[tx][ty]=1;
tail++;
}
if(mape[tx][ty]==2){
fage=1;
break;
}
}
if(fage==1){
break;
}
head++;
}
cout<<a[tail-1].s;
}
使用深度优先遍历办法
#include<bits/stdc++.h>
using namespace std;
int a[4]={0,1,0,-1};
int b[4]={1,0,-1,0};
int mina=99999;
int s[6][6]={
0,0,0,0,0,1,
0,0,0,0,1,0,
1,0,0,0,1,1,
0,1,0,0,0,0,
0,1,0,1,0,0,
0,0,0,0,0,0
};
int tx,ty;
void dfs(int x,int y,int step){
if(x==5&&y==5){
if(mina>step){
mina=step;
}
return;
}
for(int i=0;i<4;i++){
tx=x+a[i];
ty=y+b[i];
if(tx>=6||tx<0||ty>=6||ty<0)continue;
if(s[tx][ty]==0){
s[tx][ty]=1;
dfs(tx,ty,step+1);
s[tx][ty]=0;
}
}
}
int main(){
dfs(0,0,0);
cout<<mina;
}
3.七巧板着色
参考
解题思路：
1.首先将七巧板的版块使用邻接矩阵表示
{0,1,0,0,1,0,1},
{1,0,0,1,0,1,0},
{0,0,0,0,1,0,1},
{0,1,1,0,0,1,1},
{1,0,0,0,0,0,1},
{0,1,0,1,0,0,0},
{1,0,1,1,1,0,0}
2.接着使用深度优先搜索
#include<bits/stdc++.h>
using namespace std;
const int n=7;
const int data[n][n] =
{
{0,1,0,0,1,0,1},
{1,0,0,1,0,1,0},
{0,0,0,0,1,0,1},
{0,1,1,0,0,1,1},
{1,0,0,0,0,0,1},
{0,1,0,1,0,0,0},
{1,0,1,1,1,0,0}
};
int color[n]={0,0,0,0,0,0,0};
int total;
//检查相邻的版块是否颜色相同
int check(int s){
int flag=0;
for(int j=0;j<s;j++){
if(data[j][s]==1&&color[j]==color[s]){
flag=1;
}
}
return flag;
}
//使用深度搜索遍历
int dfs(int s){
//如果s==7，则7块板全部搜索完毕
if(s==7){
for(int i=0;i<n;i++){
cout<<color[i];
}
total++;
cout<<endl;
}
else{
for(int i=1;i<=4;i++){
color[s]=i;
if(check(s)==0){
dfs(s+1);
}
}
}
}
int main(){
total=0;
dfs(0);
cout<<total;
}
4.素数回环问题
1到n个数字摆成一个环，要求相邻的两个数字和是一个素数。
#include<bits/stdc++.h>
using namespace std;
int check_1[100];//用于检测当前数字是否被使用
int a[100];存放数字数组
int n=0;
//检测两数相加是否为素数
int check(int k){
int i,j;
n=(int)sqrt(k);
for(i=2;i<=n;i++){
if(k%1==0){
return 0;
}
}
return 1;
}
int dfs(int step){
//半段第一个数字和最后一个数字和是否为素数
if(step==n&&check(a[0]+a[n-1])==1){
for(int i=0;i<n;i++){
cout<<a[i]<<' '<<endl;
}
}
else{
for(int i=2;i<=n;i++){
//如果当前数字没被用过并且与前一个数字相加为素数
if(check_1[i]==0&&check(a[step-1]+i)==1){
check_1[i]=1;
a[step]=i;
dfs(step+1);
check_1[i]=0;
}
}
}
}
int main(){
cin>>n;
a[0]=1;
check_1[1]=1;
dfs(1);
return 0;
}