深度优先搜索（DFS）和广度优先搜索（BFS）

深度优先搜索（DFS）

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次. 从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。 ————摘自<深度优先搜索>《百度百科》

从百科的摘要我们可以知道，深度优先搜索（以下简称深搜）的思想其实很简单，就是“不撞南墙不回头”，以下是详细讲述：一棵树以一颗树举例。从1出发，1有两个子结点2和3，按顺序来先走到2，2有两个子结点4和5，按顺序来先走到4。 4没有子结点，也就是说已经走到头了，“撞墙”了，所以得回头了。那么我们回到2，寻找下一个未遍历的子结点也就是5，5没有子结点，于是回头。此时2的两个结点都已经走过了，所以要继续回头，回到1…… 因此深搜对该图的遍历顺序应该是： 1 2 4 5 3 6 7 放在二叉树里其实就是先序遍历。

代码实现

用矩阵表示这棵树（这里只是为了方便），t[a][b]指的是b是a的子结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>
using namespace std;
int sum;//遍历的点数
int t[8][8];//树
void dfs(int x){
	sum++;//点数+1
	for(int i=1;i<=7;i++){//按顺序遍历子结点
		if(t[x][i]==1)//如过i是x的子结点
			dfs(i);//往下走到i，递归
	}
}
int main(){
	int z;
	for(int i=1;i<=7;i++)//输入树
		for(int j=1;j<=7;j++)
			cin>>t[i][j];
	dfs(1);//深搜
	cout<<sum<<endl;//输出遍历的点数
	return 0;
} 

广度优先搜索（BFS）

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。 BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。 ——摘自<广度优先搜索>百度百科

广度优先搜索（后面简称广搜）的思想就像石子丢进湖里以后，从一个点一圈一圈往外扩散的涟漪。一棵树还是用这棵树举例。我们从1出发。将1的子结点2和3放到队列里，此时队列里的顺序是： 2 3 从队列里取出一个结点2，将2的两个子结点4和5放进队列里，此时队列里的顺序是： 3 4 5 从队列里取出一个结点3，将3的两个子结点6和7放进队列里，此时队列里的顺序是： 4 5 6 7 从队列里取出一个结点4，它没有子结点，此时队列里的顺序是： 5 6 7 …… 广搜遍历这棵树的顺序是1 2 3 4 5 6 7

代码实现

仍然是用矩阵表示这棵树，t[a][b]指的是b是a的子结点。实现了输入目的结点，输出到达结点的最短步数的功能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <iostream>
#include <queue>
using namespace std;
int z;//目的结点
int t[8][8];//树
struct point
{
	int x,step;//x是结点名，step是走到该点的步数
};
point bfs()
{
	point now,next;//目前的点，下一个点 
	now.x=1,now.step=0; //起始结点
	queue<point> q;//新建队列
	q.push(now);//将初始结点放进队列
	while(!q.empty())
	//如果队列非空，或者说还有结点未到达过
	{
		now=q.front();
		q.pop();//取出队列第一个结点
		if(now.x==z)//如果到达目的结点，结束
			return now;
		for(int i=1;i<=7;i++)
		{
			if(t[now.x][i]==1)//找到当前结点的子结点
			{
				next.x=i;
				next.step=now.step+1;
				//子结点的步数等于当前节点步数+1
				q.push(next);//子结点放进队列
			}
		}
	}
	return now;
}
int main(){
	for(int i=1;i<=7;i++)//输入
		for(int j=1;j<=7;j++)
			cin>>t[i][j];
	cin>>z;
	point end;//终点结点
	end=bfs();
	cout<<end.step<<endl;
	return 0;
} 

一般情况下，可以发现，队列中的点的步数不会相差超过1，且必然是排在前面的比排在后面的步数少（按照队列先进先出的原则必定是先处理完步数为n的结点才会轮到步数为n+1的结点），因此广搜可以找到从起点到终点的最短路径。