图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历

通常情况下图的遍历方式有两种：深度优先遍历（Depth First Search）和广度优先遍历（Breadth First Search）

---

深度优先遍历（DFS）

        从起点出发，沿着一条路径走到头(没有未被访问的节点了)，再回溯到上一个顶点，然后选择其他路径继续深入，直到遍历完所有顶点。

        实现方式：栈 / 递归（此处代码均使用递归实现）

仅遍历图中所有节点的代码如下：

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

//邻接边表节点结构 
struct Edge{
	int end;
	int weight;
};

vector<bool> isVisited;//标记对应下标的节点是否被访问过 

void dfs(vector<vector<Edge>> &G,int x){
	//当前节点已访问过，返回 
	if(isVisited[x]){
		return;
	}
	
	isVisited[x]=true;
	
	cout<<"当前访问节点："<<x<<endl;
	//遍历当前顶点的所有邻接顶点 
	for(int i=0;i<G[x].size();i++){
		int en = G[x][i].end;
		
		if(!isVisited[en]){
			dfs(G,en);
		}
	}
}

int main(){
	int n;//顶点数
	int m;//边数
	
	cin>>n;
	cin>>m;
	
	isVisited.resize(n+1,false);
	vector<vector<Edge>> G(n+1);//邻接边表存图
	
	//输入边
	for(int i=0;i<m;i++){
		int st,en,wei;//起点 终点 权值
		
		cin>>st>>en>>wei;
		G[st].push_back({en,wei}); 
	} 
	
	cout<<endl;
	cout<<"DFS遍历结果如下："<<endl;
	//遍历每个节点 
	for(int i=1;i<=n;i++){
		if(!isVisited[i]){
			dfs(G,i);
		}
	}
	
	return 0;
}

在做题时，DFS经常被用于处理走迷宫等需要找出符合条件的路径的问题，此处借助力扣的一道题200. 岛屿数量来帮助理解。

题干是这样的：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

读题中信息可知，我们可以将二维网格放置在二维数组构成的图中，从图的左上角开始向右下角遍历（因为这样遍历符合下标递增顺序），定义ans存储岛屿数量，每当遍历到一处岛屿时就将ans+1，当遍历完整个图（下标遍历到了最大值）后输出ans即可

算法实现伪代码如下：

vector<vector<bool>> visited;//标记对应下标位置是否被访问过
int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };//方向数组

void dfs(vector<vector<char>>& grid, int row, int col) {
	//若当前位置已经访问过，则直接返回
	if (visited[row][col]) {
		return;
	}
	//若当前位置是海洋，则直接返回
	if (grid[row][col] == '0') {
		return;
	}

	int n = grid.size();//行边界
	int m = grid[0].size();//列边界

	visited[row][col] = true;//标记当前位置已访问
	//访问当前位置四周的单元格
	for (int i = 0; i < 4; i++) {
		int dx = row + dir[i][0];
		int dy = col + dir[i][1];

		if (dx >= 0 && dx < n && dy >= 0 && dy < m && !visited[dx][dy]) {
			dfs(grid, dx, dy);
		}
	}
}

int numIslands(vector<vector<char>>& grid) {
	int n = grid.size();//行
	int m = grid[0].size();//列

	//初始化visited数组全为false
	visited.resize(n, vector<bool>(m));

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//若当前位置是岛屿且未被访问过，ans++
			if (grid[i][j] == '1' && !visited[i][j]) {
				dfs(grid, i, j);
				ans++;
			}
		}
	}

	return ans;
}

根据这道题，我们可以总结出一个适用于迷宫找路径等问题的dfs模版来，大致如下：

void dfs(图，当前顶点数据/顶点的坐标){
	边界判断（是否超出范围，是否已访问过，是否为题目所需的位置...） 
	
	标记当前位置已访问
	
	遍历当前位置旁边的格子(大部分情况是上下左右四个方向){
		
		 若当前格子满足条件，则对该格子进行dfs(不超出范围){
		 	dfs(图,当前位置的行坐标，当前位置的列坐标)
		 } 
	}
	
	回溯，改变该位置状态为未访问（特定题目可省略）
}

在不同的情景下所需dfs的形式可能是不同的，但其逻辑是不变的，所以需要在掌握dfs的逻辑后根据不同情景适当改变dfs的形式

---

广度优先遍历（BFS）

       从起点出发，先访问所有直接相连的邻点，再访问所有邻点的邻点，逐层扩散，直到遍历完所有的顶点。

        实现方式：队列

仅遍历图中所有节点的代码如下：

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

//邻接边表节点结构
struct Edge{
	int end;//终点
	int weight;//权值 
}; 

vector<bool> isVisited;//标记对应下标的节点是否被访问过 

void bfs(vector<vector<Edge>> &G,int x){
	queue<int> q;
	
	//起点入队 
	q.push(x);
	isVisited[x]=true;//标记该顶点为已访问状态 
	
	while(!q.empty()){
		//取出队首元素并将其出队列 
		int s = q.front();
		q.pop();
		
		cout<<"当前访问顶点："<<s<<endl;
		
		//遍历以当前顶点为起点的边的所有终点 
		for(int i=0;i<G[s].size();i++){
			//保存终点 
			Edge e = G[s][i];
			int en = e.end;
			
			//若该终点未被访问过，将其入队并标记状态为true 
			if(!isVisited[en]){
				isVisited[en]=true;
				q.push(en);
			}
		}
	}
}

int main(){
	int n,m;//顶点数 边数
	cin>>n>>m; 
	
	vector<vector<Edge>> G(n+1);
	
	for(int i=0;i<m;i++){
		int st,en,wei;
		cin>>st>>en>>wei;
		
		G[st].push_back({en,wei});
	}
	
	isVisited.resize(n+1,false);
	
	
	cout<<endl;
	cout<<"BFS遍历结果如下："<<endl;
	//遍历每个节点 
	for(int i=1;i<=n;i++){
		if(!isVisited[i]){
			bfs(G,i);
		}
	}
	
	return 0;
}

同DFS一样，BFS也经常在做题时遇到，且被用于解决求最短路径等问题，此处我们还是借助 200. 岛屿数量来帮助理解。

BFS算法实现伪代码如下：

vector<vector<bool>> visited;//标记对应下标位置是否被访问过
int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };//方向数组

void bfs(vector<vector<char>>& grid, int row, int col) {
	int n = grid.size();//行边界
	int m = grid[0].size();//列边界

	queue<pair<int,int>> q;//核心队列
	q.push({ row, col });//当前位置入队列
	visited[row][col] = true;//标记当前位置已访问

	//访问当前位置四周的单元格
	while (!q.empty()) {
		pair<int, int> s = q.front();//取出队首元素
		q.pop();//队首元素出队

		//遍历当前位置的四个方向
		for (int i = 0; i < 4; i++) {
			int dx = s.first + dir[i][0];
			int dy = s.second + dir[i][1];

			if (dx >= 0 && dx < n && dy >= 0 && dy < m && !visited[dx][dy] && grid[dx][dy] == '1') {
				//若找到岛屿，将其入队并标记状态为已访问
				q.push({ dx,dy });
				visited[dx][dy] = true;
			}
		}
	}
}

int numIslands(vector<vector<char>>& grid) {
	int n = grid.size();//行
	int m = grid[0].size();//列

	//初始化visited数组全为false
	visited.resize(n, vector<bool>(m));

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//若当前位置是岛屿且未被访问过，ans++
			if (grid[i][j] == '1' && !visited[i][j]) {
				bfs(grid, i, j);
				ans++;
			}
		}
	}

	return ans;
}

总结出的bfs模版大致如下：

void bfs(图，当前顶点的数据/当前顶点的坐标){
	queue<数据类型> q;//核心队列 
	
	//当前顶点入队并标记该顶点状态为已访问 
	q.push(当前顶点);
	Visited[当前顶点]=true;
	
	//while循环 
	while(!q.empty()){
		//取出队首元素并将其出队列 
		数据类型 vertex = q.front();
		q.pop();
		
		//遍历
		for(int i=0;i<四周相连顶点的个数;i++){
			
			用方向数组/结构体保存周围顶点 
			
			if(限制条件){
				满足限制条件，将该顶点入队，标记该顶点状态为已访问 
			}
		}
	}
}

---

写在最后

        DFS和BFS在数据结构及算法题当中占据重要地位，应用场景很多，所以需要深入理解并掌握，希望我的博客能够帮助到大家，谢谢！