图的遍历顺序有两种
：深度优先搜索（
DFS
）和广度优先搜索（
BFS
）
深度优先算法思想DFS
深度优先搜索遍历类似于树的先序遍历。
假定给定图
G
的初态是所有顶点均未被访问过，在
G
中任选一个顶点
i
作为遍历的初始点，则深度优先搜索递归调用包含以下操作：
（
1
）访问搜索到的未被访问的邻接点；
（
2
）将此顶点的
visited
数组元素值置
1
；
（
3
）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。
深度优先搜索
DFS
可描述为：
（
1
）访问
v0
顶点；
（
2
）置
visited[v0]=1
；
（
3
）搜索
v0
未被访问的邻接点
w
，若存在邻接点
w
，则
DFS(w)
。
遍历过程：
DFS
在访问图中某一起始顶点 v
后，由 v
出发，访问它的任一邻接顶点 w1
；再从 w1
出发，访问与 w1
邻
接但还没有访问过的顶点 w2
；然后再从 w2
出发，进行类似的访问，…
如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u
为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
例题1：
方格填数
如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
#include <stdio.h>
#include <cmath>
using namespace std;
int flag[3][4]; //表示哪些位置可以填数
int mpt[3][4]; //填数
bool visit[10]; //没赋值，默认是false
int ans = 0;
void init() //初始化
{
int i,j;
for(i = 0 ; i < 3 ; i ++)
for(j = 0 ; j < 4 ; j ++)
flag[i][j] = 1;
flag[0][0] = 0; //边缘化处理
flag[2][3] = 0;
}
void Solve() //判断填的数是否满足要求
{
int dir[8][2] = { 0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
int book = true;
for(int i = 0 ; i < 3 ; i ++)
{
for(int j = 0 ; j < 4; j ++)
{
//判断每个数周围是否满足
if(flag[i][j] == 0) continue;
for( int k = 0 ; k < 8 ; k ++)
{
int x,y;
x = i + dir[k][0];
y = j + dir[k][1];
if(x < 0 || x >= 3 || y < 0 || y >= 4 || flag[x][y] == 0) continue; //如果超界或者这个位置是两个角则进行下一个位置的判断
if(abs(mpt[x][y] - mpt[i][j]) == 1) book = false; //如果相邻的是紧挨着的数 则不满足条件
}
}
}
if(book) ans ++;
}
void dfs(int index)
{
int x,y;
x = index / 4; //巧妙的写出了3*4表格的坐标
y = index % 4;
if( x == 3) //已经填满数，判断填上的数是否满足要求
{
Solve();
return;
}
if(flag[x][y]) //表示这个位置可以填数
{
for(int i = 0 ; i < 10 ; i ++)
{
if(!visit[i]) //如果这个数没有用过
{
visit[i] = true;//表示这个数暂时用了
mpt[x][y] = i;
dfs(index+1); //一直深下去，直到返回来
visit[i] = false; //返回来之后把数又重新置假，表示没用过这个数 以此来完成填的数的不同
}
}
}
else
{
dfs(index+1);
}
}
int main()
{
bool vi[10];
for(int i=0; i<10; i++)
printf("%d ",vi[i]);
init();
dfs(0);
printf("%d\n",ans);
return 0;
}
BFS遍历
BFS思想
1.从初始状态S开始，利用规则，生成下一层的状态。
2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状 态节点。
3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树
BFS框架
例题 ：迷宫问题(最短路径)-BFS
代码：
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
int maze[6][6];
int visit[6][6]; //判断是够拜访过这个点
int dis[6][6]; //标记步数
int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
struct node
{
int x;
int y;
};
queue <node> p;
int nyj(int a,int b)
{
if(a>=0 && a<5 && b>=0 && b<5) return 1;
else return 0;
}
void print(int i,int j)
{
if(i==0 && j==0)
{
printf("(%d, %d)\n",i,j);
return ;
}
for(int x=0;x<4;x++)
{
int xx=i+dir[x][0];
int yy=j+dir[x][1];
if(nyj(xx,yy) && !maze[xx][yy] && dis[xx][yy]==dis[i][j]-1)
print(xx,yy);
}
printf("(%d, %d)\n",i,j);
}
void BFS(int i,int j)
{
node n;
n.x=i; n.y=j;
p.push(n);
dis[i][j]=1;
visit[i][j]=1;
while(!p.empty())
{
n=p.front();
p.pop();
for(int x=0;x<4;x++)
{
int xx=n.x+dir[x][0];
int yy=n.y+dir[x][1];
if(nyj(xx,yy) && maze[xx][yy]==0 && !visit[xx][yy]) {
visit[xx][yy] =1;
dis[xx][yy]=dis[n.x][n.y]+1;
node a;
a.x=xx; a.y=yy;
p.push(a);
}
}
}
print(4,4);
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>maze[i][j];
memset(visit,0,sizeof(visit));
memset(dis,0,sizeof(dis));
BFS(0,0);
return 0;
}
