BFS and DFS

First Post:

2022-11-03

Last Update:

2023-03-15

Word Count:

1.2k

Read Time:

5 min

BFS广度优先遍历和DFS深度优先遍历

广度优先搜索(Breadth First Search，简称BFS)

假设从A节点出发，在访问了该节点之后依次访问这个节点各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点。重复此步骤，直到所有的节点都被访问完为止。

如上图，广度优先搜索的顺序是：ABCDEFG

深度优先搜索(Depth First Search，简称DFS)

假设从A节点出发，首先访问该节点，然后依次从它的各个未被访问的邻接点出发，访问邻接点的邻接点。重复此步骤，直到所有的节点都被访问完为止。

如上图，深度优先搜索的顺序是：ABDECFG

实战

现在以一个实际的例子用C#代码来实现，下面是Unity中的一个Hierarchy层级图，根节点是Root，下面有GameObject，GameObject (1)， GameObject (2)三个节点，其中GameObject (1)下又有GameObject_A和GameObject_B两个节点：

using System.Collections.Generic;
using UnityEngine;

public class DM06Composite : MonoBehaviour
{
    void Start()
    {
        DMComposite root = new DMComposite("Root");
        // 添加Root下的三个节点
        DMLeaf leaf1 = new DMLeaf("GameObject");
        DMLeaf leaf2 = new DMLeaf("GameObject (2)");
        DMComposite gameObject1 = new DMComposite("GameObject (1)");
        root.AddChild(leaf1);
        root.AddChild(gameObject1);
        root.AddChild(leaf2);
        
        // 添加GameObject (1)下面的两个节点
        DMLeaf child1 = new DMLeaf("GameObject_A");
        DMLeaf child2 = new DMLeaf("GameObject_B");
        gameObject1.AddChild(child1);
        gameObject1.AddChild(child2);

        // 按照广度优先或深度优先输出节点顺序
        //DepthFirstSearch(root);
        BreadthFirstSearch(root);
    }

    // 广度优先检索
    private void BreadthFirstSearch(DMComponent component)
    {
        Queue<DMComponent> q = new Queue<DMComponent>();
        q.Enqueue(component);
        // 打印节点名字
        Debug.Log(component.Name);
        while (q.Count > 0)
        {
            DMComponent temp = q.Dequeue();
            List<DMComponent> children = temp.Children;
            foreach (DMComponent child in children)
            {
                // 打印节点名字
                Debug.Log(child.Name);
                q.Enqueue(child);
            }
        }
    }

    // 深度优先检索
    private void DepthFirstSearch(DMComponent component)
    {
        // 打印节点名字
        Debug.Log(component.Name);
        List<DMComponent> children = component.Children;
        if (children == null || children.Count == 0) return;
        foreach (DMComponent child in children)
        {
            DepthFirstSearch(child);
        }
    }
}

// 抽象组件类
public abstract class DMComponent
{
    protected string mName;
    public string Name { get { return mName; } }
    public DMComponent(string name)
    {
        mName = name;
        mChildren = new List<DMComponent>();
    }
    protected List<DMComponent> mChildren;
    public List<DMComponent> Children { get { return mChildren; } }
    public abstract void AddChild(DMComponent c);
    public abstract void RemoveChild(DMComponent c);
    public abstract DMComponent GetChild(int index);
}

// 叶子类，一棵树当中没有子节点的节点
public class DMLeaf : DMComponent
{
    public DMLeaf(string name) : base(name) { }


    public override void AddChild(DMComponent c)
    {
        return;
    }

    public override void RemoveChild(DMComponent c)
    {
        return;
    }

    public override DMComponent GetChild(int index)
    {
        return null;
    }
}

// 容器类，可以有子节点
public class DMComposite : DMComponent
{
    public DMComposite(string name) : base(name) { }


    public override void AddChild(DMComponent c)
    {
        mChildren.Add(c);
    }

    public override void RemoveChild(DMComponent c)
    {
        mChildren.Remove(c);
    }

    public override DMComponent GetChild(int index)
    {
        return mChildren[index];
    }
}