序

DFS和BFS是很常见的遍历算法，通常用于遍历图或者树。著名的游戏“泡泡龙”就可以用DFS或者BFS来实现泡泡消除，本篇文章将介绍DFS和BFS的原理，以及在C#下的实现方式，最后在简单结合制作一款独特的泡泡龙游戏。

本文拥有教学视频，你可以在抖音（点击）或者B站（点击）获取更详细清晰的视频讲解，与此同时你可以在GitHub（点击）获取本文项目的完整代码。

什么是DFS和BFS？

简单来说，DFS和BFS是一种用来遍历图和树的算法。

DFS（深度优先算法）

顾名思义，DFS优先把一条路径探索到最底，也就说会一直探索下去，遇到死路则返回上一个路口换路探索，以此类推

实现方法

通过栈（后进先出）实现，以下为C#代码：

        HashSet<Cube> visited = new HashSet<Cube>(); //用于存储已经访问过的节点
        Stack<Cube> stack = new Stack<Cube>();       //栈
        stack.Push(cube);  //首元素进栈                                
        while (stack.Count > 0) //只要栈非空，就循环
        {
            Cube currentCube = stack.Pop(); //从栈中取得一个节点
            if (!visited.Contains(currentCube)) //判断是否访问过该节点
            {
                //对该节点操作
                visited.Add(currentCube); //存储已访问节点             
            }
            foreach (Cube neighbour in currentCube.neighbours) //遍历该节点的邻居节点
            {
                if (!visited.Contains(neighbour)) //未访问邻居节点进栈
                {
                    stack.Push(neighbour);
                }
            }
        }

注：对于存储已访问过的节点，使用HashSet是很适合，因为HashSet是借助哈希表实现，本质上可以保证容器内元素的唯一性

BFS（广度优先算法）

同样顾名思义，BFS优先探索每一个分支，每遇到一个分支节点，则会把该节点下的每个分支优先探索一遍

实现方法

通过队列（先进先出）实现，以下为C#代码：

        HashSet<Cube> visited = new HashSet<Cube>(); //用于存储已经访问过的节点
        Queue<Cube> queue = new Queue<Cube>();       //队列
        queue.Enqueue(cube);  //首元素入队
        while (queue.Count > 0) //只要队列非空，就循环
        {
            Cube currentCube = queue.Dequeue(); //从队列中取得一个节点
            if (!visited.Contains(currentCube)) //判断是否访问过该节点
            {
                //对该节点操作
                visited.Add(currentCube); //存储已访问节点 
            }
            foreach (Cube neighbour in currentCube.neighbours) //遍历该节点的邻居节点
            {
                if (!visited.Contains(neighbour)) //未访问邻居节点进队列
                {
                    queue.Enqueue(neighbour);
                }
            }
        }

为什么需要DFS和BFS

当你需要对一个树或者一个图进行遍历的时候，通常会考虑使用类似于数组遍历的方法，但是图和树相对于数组来说是二维的，并不能通过简单的For循环进行遍历，于是便需要DFS和BFS

DFS和BFS不同的区别

从实现方法我们可以发现，DFS和BFS的代码是高度相似的，其最大的不同即使用的容器的区别

DFS依托于栈“后进先出”的特点，优先对单条路径进行探索，即一条路走到尽头再回到上一个分支

而BFS是基于队列“先进先出”的特点，优先对当前节点的每个分支进行探索，更适合于探索最短路径（下一章知识）

“泡泡龙”游戏如何使用DFS和BFS？

“泡泡龙”游戏在消除泡泡时需要进行计算，泡泡是一种很典型的图，也可以看作是一个节点，以下代码即最基础的泡泡：

public class Cube : MonoBehaviour
{
    public CubeColor cubeColor; //泡泡颜色
    public bool isRoot = false; //是否是根节点
    public List<Cube> neighbours = new List<Cube>(); //邻居节点（这个也可以使用HashSet）
}

泡泡的消失算法

泡泡的消失一共有两部分：第一部分是发射的泡泡与场景中的泡泡产生的直接作用，第二部分是根节点消失导致的间接作用

直接作用产生的消失

直接作用是很典型的图遍历，我们只需要在DFS或者BFS的基础进行更改即可，由于篇幅问题，这里只放了DFS的代码，BFS实现的代码你可以在GitHub中的项目文件的CubeManager的PaoPaoLong_BFS_Animation函数中找到

我比较推荐使用BFS来进行遍历，以防止DFS的栈溢出导致程序无法运行的问题

下文所采用的算法和洪水填充算法大同小异，最大的区别是洪水填充算法是基于二维数组，而下文的算法的算法是基于泡泡节点的List<Cube>neighbours 容器，该项目在建立之初依然设计了二维数组存储泡泡，因此感兴趣的朋友可以在此基础上进行洪水算法的开发

以下代码通过DFS遍历并存储发射泡泡所链接的同色泡泡，若数量大于3个则进行销毁

        //以下代码:找出Cube和附近颜色相同的，大于3个就全部消失
        //代码和上方的DFS算法大量重合，因此只介绍更改部分
        //cube是该方法的参数，外部传入，意为发射的泡泡
        HashSet<Cube> disableSet = new HashSet<Cube>(); //这是原来存放已访问的容器，这里用于存放需要消失的泡泡
        Stack<Cube> stack = new Stack<Cube>();
        stack.Push(cube);
        while (stack.Count > 0)
        {
            Cube currentCube = stack.Pop();
            if (!disableSet.Contains(currentCube))
            {
                disableSet.Add(currentCube);
            }
            foreach (Cube neighbour in currentCube.neighbours)
            {
                //以下判断泡泡是否启用，并且颜色与发射泡泡的颜色是否相同
                if (!disableSet.Contains(neighbour) && neighbour.isEnable && neighbour.cubeColor == cube.cubeColor)
                {
                    stack.Push(neighbour);
                }
            }
        }
        if (disableSet.Count < 3) //少于三个相同颜色的相邻泡泡即不做处理
        {
            isWorking = false;
            yield break;
        }
        foreach (Cube currentCube in disableSet) //遍历待消失容器，进行销毁
        {
            yield return new WaitForSeconds(waitTime);
            currentCube.DisableCube();
        }
        disableSet.Clear();

间接作用产生的消失

间接消失是由于某堆泡泡的根节点消失导致该堆泡泡没有支点所产生的，因此最重要的是判断某堆泡泡是否是根泡泡的支系

以下代码通过所有的根泡泡来遍历所有泡泡，不在访问记录中泡泡即不在根支系中，也就是需要销毁的泡泡

        HashSet<Cube> rootSet = new HashSet<Cube>();  //根容器
        HashSet<Cube> cubesSet = new HashSet<Cube>(); //所有泡泡的容器
        HashSet<Cube> visited = new HashSet<Cube>();  //已经访问过的容器
        //以下代码通过所有根泡泡遍历并存储其支系泡泡
        foreach (Cube root in rootSet) //遍历根泡泡
        {
            stack = new Stack<Cube>();
            stack.Push(root);
            while (stack.Count > 0)
            {
                Cube currentCube = stack.Pop();
                if (!visited.Contains(currentCube) && currentCube.isEnable)
                {
                    visited.Add(currentCube);
                }
                foreach (Cube neighbour in currentCube.neighbours)
                {
                    if (!visited.Contains(neighbour) && neighbour.isEnable)
                    {
                        stack.Push(neighbour);
                    }
                }
            }
        }
        //以下是一个差运算，即所有泡泡集合-已经访问过的泡泡集合=需要销毁的泡泡集合
        //进行差运算方法不止一种，这里方法比较笨
        foreach (Cube currentCube in cubesSet)
        {
            if (!visited.Contains(currentCube))
            {
                disableSet.Add(currentCube);
            }
        }
        //以下代码销毁泡泡
        foreach (Cube currentCube in disableSet)
        {
            yield return new WaitForSeconds(waitTime);
            currentCube.DisableCube();
        }

根据如上的两种计算，即可实现泡泡的消失

预

下一期我将通过制作一款简单2D游戏，介绍一下Dijkstra和A*算法，下期见！