BFS、DFS - 学习小记 - 计算机科学 | Red-Leaf = 永远少年！ = 吹灭读书灯，一身都是月

# BFS 是 Breadth-First Search 的缩写，称为广度优先搜索，或宽度优先搜索。

1.1 搜索方式

步骤 1：从源点出发，访问源点的邻居结点，将邻居节点依次放入队列中，并标记为已访问；

步骤 2：取出队列中的邻居结点，依次访问每个节点未被访问的邻居节点；

步骤 3：将邻居节点依次放入队列中，并标记为已访问；

步骤 4：重复步骤 2~3 直到访问到目标节点或所有节点都标记为已访问。
算法代码：

	#include<iostream>
	#include<queue>
	using namespace std;

	int a[11][11];
	bool visited[11];

	void store_graph()
	{
	for(int i=1;i<=10;i++)
	for(int j=1;j<=10;j++)
	cin>>a[i][j];
	}

	void bfs_graph()
	{
	void bfs(int v);

	memset(visited,false,sizeof(visited));

	for(int i=1;i<=10;i++)
	if(visited[i]==false)
	bfs(i);
	}

	void bfs(int v)
	{
	int Adj(int x);

	queue<int> myqueue;
	int adj,temp;

	cout<<v<<" ";
	visited[v]=true;
	myqueue.push(v);

	while(!myqueue.empty()) // 队列非空表示还有顶点未遍历到
	{
	temp=myqueue.front(); // 获得队列头元素
	myqueue.pop(); // 头元素出对

	adj=Adj(temp);
	while(adj!=0)
	{
	if(visited[adj]==false)
	{
	cout<<adj<<" ";
	visited[adj]=true;
	myqueue.push(adj); // 进对
	}

	adj=Adj(temp);
	}
	}
	}

	int Adj(int x)
	{
	for(int i=1;i<=10;i++)
	if(a[x][i]==1 && visited[i]==false)
	return i;

	return 0;
	}

	int main()
	{
	cout<<"初始化图:"<<endl;
	store_graph();

	cout<<"bfs遍历结果:"<<endl;
	bfs_graph();

	return 0;
	}

# DFS 是 Depth-First-Search 的缩写，称为深度优先搜索。

2.1 搜索方式

步骤 1：从源点出发，访问源点的某个邻居节点，将其放入栈中，并标记为已访问；

步骤 2：从栈中取出一个节点，访问该节点的未被访问的邻居节点；

步骤 3：将邻居节点放入栈中，并标记为已访问；

步骤 4：重复步骤 2 ~ 3，直到访问到目标节点或所有节点都标记为已访问；
算法代码：

	#include<iostream>
	using namespace std;

	int a[11][11];
	bool visited[11];

	void store_graph() // 邻接矩阵存储图
	{
	int i,j;

	for(i=1;i<=10;i++)
	for(j=1;j<=10;j++)
	cin>>a[i][j];
	}

	void dfs_graph() // 深度遍历图
	{
	void dfs(int v);

	memset(visited,false,sizeof(visited));

	for(int i=1;i<=10;i++) // 遍历每个顶点是为了防止图不连通时无法访问每个顶点
	if(visited[i]==false)
	dfs(i);
	}

	void dfs(int v) // 深度遍历顶点
	{
	int Adj(int x);

	cout<<v<<" "; // 访问顶点 v
	visited[v]=true;

	int adj=Adj(v);
	while(adj!=0)
	{
	if(visited[adj]==false)
	dfs(adj); // 递归调用是实现深度遍历的关键所在

	adj=Adj(v);
	}
	}

	int Adj(int x) // 求邻接点
	{
	for(int i=1;i<=10;i++)
	if(a[x][i]==1 && visited[i]==false)
	return i;

	return 0;
	}

	int main()
	{
	cout<<"初始化图:"<<endl;
	store_graph();

	cout<<"dfs遍历结果:"<<endl;
	dfs_graph();

	return 0;
	}

# bfs 和 dfs 的区别

1、数据结构

bfs 遍历节点是先进先出，一般使用队列作为辅助数据结构，dfs 遍历节点是先进后出，一般使用栈作为辅助数据结构；
2、访问节点的方式

bfs 是按层次访问的，先访问源点，再访问它的所有相邻节点，并且标记结点已访问，根据每个邻居结点的访问顺序，依次访问它们的邻居结点，并且标记节点已访问，重复这个过程，一直访问到目标节点或无未访问的节点为止。

dfs 是按照一个路径一直访问到底，当前节点没有未访问的邻居节点时，然后回溯到上一个节点，不断的尝试，直到访问到目标节点或所有节点都已访问。
3、应用

bfs 适用于求源点与目标节点距离近的情况，例如：求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况，例如：全排列、拓扑排序、求到达某一点的任意一条路径。
BFS 常用于找单一的最短路线，它的特点是 "搜到就是最优解"，而 DFS 用于找所有解的问题，它的空间效率高，而且找到的不一定是最优解，必须记录并完成整个搜索，故一般情况下，深搜需要非常高效的剪枝（通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些 “枝条”，故称剪枝）

学习心得

# BFS 是 Breadth-First Search 的缩写，称为广度优先搜索，或宽度优先搜索。

# DFS 是 Depth-First-Search 的缩写，称为深度优先搜索。

# bfs 和 dfs 的区别

动态规划

编程竞赛模式介绍