深度优先及广度优先在Unity中的应用

深度优先遍历是按照树（图）的深度遍历的一种遍历算法。主要是基于深度优先，既是从某一节点V做为起始节点开始进行遍历，当V的的某一边里全部都遍历事后，回溯到起始节点V，而后继续对另外一条边进行遍历，直至全部节点被遍历完成为止。

如上图所示的树，深度优先的遍历方式为：

1. A做为Root结点，第一个被访问，而后依次访问B、E、K，当这条路走完后，接着访问L，而后访问F，这样就表明第一条边被访问完成；
2. 而后回溯到A，依次访问C、G
3. 最后在回溯到A，依次访问D、H、M、I、J

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// 

/// 深度优先
/// 
public class DepthFirst : MonoBehaviour
{
    //用于存储所遍历到的物体
    List DepthFirstList = new List();
    
    void Start()
    {
        DepthFirst_0(transform);
        //打印序列
        foreach (var item in DepthFirstList)
        {
            Debug.Log(item);
        }
    }

    void DepthFirst_0(Transform tran)
    {
        foreach (Transform item in tran)
        {
            DepthFirstList.Add(item);
            //判断是否存在子物体
            if (item.childCount != 0)
            {
                DepthFirst_0(item);
            }
        }
    }
}

打印结果以下所示：

 

广度优先遍历是按照树（图）的广度遍历的一种遍历算法（又称为层次遍历）。主要是基于广度优先，既是某一节点V做为起始节点开始进行遍历，沿着树（图）的层次进行依次遍历，当第N层被遍历完成后，进行第N+1层遍历，当全部节点都比访问后，遍历完成。

如上图所示的树，广度优先的遍历方式为：

1. A做为Root结点，做为第一层被访问，当第一层访问完成，切到第二层
2. 而后依次访问第二层：B、C、D，第二层访问完成
3. 而后依次访问第三层：E、F、G、H、I、J，第三层访问完成
4. 而后依次访问第四层：K、L、M
5. 没有第4+1层，遍历完成

在Unity中广度遍历全部子物体以下所示：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// 

/// 获取全部关键
/// 
public class BreathFirst : MonoBehaviour
{
    List BreadthFirstList = new List();//层次遍历所获得的List

    /// 

    /// 首先把物体的第一层子物体放入一个List，便于以后使用
    /// 
    void Start()
    {
        List joinsList = new List();
        foreach (Transform itemJoins in transform)
        {
            joinsList.Add(itemJoins);
        }
        BreadthFirst_1(joinsList);

        foreach (var item in BreadthFirstList)
        {
            Debug.Log(item);
        }
    }

    /// 

    /// 递归遍历每一层
    /// 
    /// 
    void BreadthFirst_1(List joins)
    {
        List joinsChildListss = new List();
        foreach (Transform item in joins)
        {
            BreadthFirstList.Add(item);//将每一层依次放入列表中
            if (item.childCount != 0)//判断每一次的序列项是否存在子物体，存在就将全部子物体放入一个新的List
            {
                foreach (Transform itemss in item)
                {
                    joinsChildListss.Add(itemss);
                }
            }
        }
        if (joinsChildListss != null && joinsChildListss.Count != 0)//判断是不是最后一层
            BreadthFirst_1(joinsChildListss);
    }
}

打印结果以下所示：

深度优先算法是对物体的深度上进行的遍历，广度优先算法是对物体广度上的遍历，若是当咱们想要获得物体的层级关系（如：文件件的全部层级关系，3D 人物的骨骼关键关系等）时，咱们能够将深度优先结合广度优先便可获得整个层级关系——经过深度优先遍历获取获得每一个节点的深度信息，经过广度优先遍历获取到每一个节点的广度信息。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// 

/// 获取全部关键
/// 
public class ListOfJoints : MonoBehaviour
{
    public Transform HumModel;
    int numCount = 0;
    List BreadthFirstList = new List();
    Dictionary BreathFirstDic = new Dictionary();
    List DepthFirstList = new List();
    IEnumerator Start()
    {
        yield return new WaitForEndOfFrame();
        DepthFirst_0(HumModel);
        BreadthFirst_0(HumModel);
        yield return new WaitForEndOfFrame();
        foreach (var item in DepthFirstList)
        {
            if (BreathFirstDic.ContainsKey(item))
            {
                string str = "";
                for (int i = 0; i  joinsList = new List();
        foreach (Transform itemJoins in HumModel)
        {
            joinsList.Add(itemJoins);
        }
        BreadthFirst_1(joinsList);
    }
    void BreadthFirst_1(List joins)
    {
        numCount++;//层数
        List joinsChildListss = new List();
        foreach (Transform item in joins)//打印子物体
        {
            BreadthFirstList.Add(item);
            BreathFirstDic.Add(item, numCount);
            if (item.childCount != 0)
            {
                foreach (Transform itemss in item)
                {
                    joinsChildListss.Add(itemss);
                }
            }
        }
        if (joinsChildListss != null && joinsChildListss.Count != 0)
            BreadthFirst_1(joinsChildListss);
    }
    void DepthFirst_0(Transform tran)
    {
        foreach (Transform item in tran)
        {
            DepthFirstList.Add(item);
            if (item.childCount != 0)
            {
                DepthFirst_0(item);
            }
        }
    }


}