算法笔记——深度/广度优先搜索

算法笔记——深度/广度优先搜索

深度优先搜索和广度优先搜索主要是用在图的遍历中，模板性很强，我个人认为是比较简单的算法，下面主要写一下深搜和广搜的模板，照着模板多做题基本就能掌握了

深度优先搜索 过程：

1. 访问指定的起始顶点
2. 若当前访问的顶点的邻接顶点有未被访问的,则选择其中一个顶点访问，然后回到第一步
3. 若当前的顶点的邻接顶点都已经访问，则返回当前顶点的上一个顶点

如下图，其实就是先沿一条边访问到底，然后再返回访问另一条边

模板

DFS一般通过递归来实现

 void dfs(int x){
    if (满足退出条件){ 
        退出处理
        return; 
    }
    for (;;){//枚举当前顶点的下一个邻接顶点
        if (顶点满足条件) {
            处理顶点
            dfs(顶点);//向下深入遍历
            }
    }
    return ;//退出 
}

这里在枚举下一个邻接顶点的时候，如果是在图中，我习惯先定义一个方向向量，然后以此来枚举下一个顶点 以上下左右四个方向为例： 首先定义：

 int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

枚举：

for (int i = 0; i