采用C#的最简单的广度优先搜索BFS和深度优先搜索DFS应用

对如下图所示的树状图利用广度优先搜索BFS和深度优先搜索DFS对各个结点进行了遍历，采用C#语言。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;


class prog
{
    static void Main(string[] args)
    {
        #region (1) 设计树的原始属性：id和邻接关系
        List<bond> ttt = new List<bond>();
        bond pp = new bond();

        pp = new bond();
        pp.id = 1;
        pp.nbs=new int[] {3,2,4};
        ttt.Add(pp);

        pp = new bond();
        pp.id = 2;
        pp.nbs = new int[] {1, 5,8,300 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 4;
        pp.nbs = new int[] { 1,6,10,200 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 3;
        pp.nbs = new int[] { 1,7,9,100 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 6;
        pp.nbs = new int[] { 4 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 10;
        pp.nbs = new int[] { 4 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 5;
        pp.nbs = new int[] {2 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 8;
        pp.nbs = new int[] {2 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 7;
        pp.nbs = new int[] { 3};
        ttt.Add(pp);

        pp = new bond();
        pp.id = 9;
        pp.nbs = new int[] { 3,400};
        ttt.Add(pp);

        pp = new bond();
        pp.id = 100;
        pp.nbs = new int[] {3 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 200;
        pp.nbs = new int[] {4 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 300;
        pp.nbs = new int[] {2 };
        ttt.Add(pp);

        pp = new bond();
        pp.id = 400;
        pp.nbs = new int[] { 9 };
        ttt.Add(pp);




        #endregion

        //(2) 广度优先搜索结果
        BFS(ttt, ttt[0]);

        Console.WriteLine("\n");

        //(3) 重置“被遍历过”的标记visited
        foreach (bond tmp in ttt)
            tmp.visited = false;

        //(4) 深度优先搜索结果
        DFS( ttt, ttt[0]);
    
        Console.ReadLine();
    }

    private static void DFS(List<bond> ttt, bond start)
    {
        //(1) LINE为最终顺序
        List<bond> LINE = new List<bond>();
        LINE.Add(start);
        
        //(2) b为一个临时存储集合
        List<bond> b = new List<bond>();
        b.Add(start);

        //(3) 设置起始元素已遍历
        start.visited = true;

        //(4) a作为一个临时指代变量
        bond a = new bond();

        //b_nbs是b[b.count-1]的邻接元素集合，未遍历过的引为a

        //(5) 当临时存储集合不为空时
        while (b.Count != 0)
        {
            //(5.1) b_nbs为b中最后一个元素（最新加入的元素，即b[b.Count - 1]）的邻接元素
            List<bond> b_nbs = new List<bond>();
            b_nbs = b[b.Count - 1].GET_NBS(ttt);

            //(5.2) a为b_nbs中第一个没有遍历过的元素，a可能不存在
            a = b_nbs.FirstOrDefault(k => !k.visited);

            //(5.3) 当b[b.Count - 1]一直存在未遍历过的邻接节点a时
            while (a != null) 
            {
                //(5.3.1) 将a放入b和LINE，并设置已遍历
                b.Add(a);
                LINE.Add(a);
                a.visited = true;

                //(5.3.2) b_nbs重新指向b中最后一个元素（最新加入的元素，即b[b.Count - 1]）的邻接元素
                b_nbs = new List<bond>();
                b_nbs = b[b.Count - 1].GET_NBS(ttt);

                //(5.3.3) a重新指向b_nbs中第一个没有遍历过的元素，a可能不存在
                a = b_nbs.FirstOrDefault(k => !k.visited);
            }

            //(5.4) 当b[b.Count - 1]不存在未遍历过的邻接节点a时，将b[b.Count - 1]从b中除去
            if (a == null)
                b.Remove(b[b.Count - 1]);
        }

        //(6) 按顺序输出元素
        foreach (bond ghj in LINE)
            Console.WriteLine("DFS:"+ghj.id);


    }

    private static void BFS(List<bond> ttt, bond start)
    {
        //核心在于理解和运用先进先出的堆栈
        //(1) LINE为最终顺序
        List<bond> LINE = new List<bond>();
        LINE.Add(start);

        //(2) qq为先进先出的堆栈
        Queue qq = new Queue();
        qq.Enqueue(start);

        //(3) 设置起始元素已遍历
        start.visited = true;

        //(4) a用于指向栈顶弹出的元素
        bond a = new bond();

        //(5) 当堆栈不为空时
        while (qq.Count != 0)
        {
            //(5.1) a用于指向栈顶弹出的元素
            a = new bond();
            a = (bond)qq.Dequeue();

            //(5.2) a_nbs为a的邻接元素集合
            List<bond> a_nbs = new List<bond>();
            a_nbs = a.GET_NBS(ttt);

            //(5.3) 将a_nbs中没有遍历过的元素放入堆栈和LINE，并设置visited
            foreach (bond tmp in a_nbs.Where(k => !k.visited).ToList())
            {
                qq.Enqueue(tmp);
                LINE.Add(tmp);
                tmp.visited = true;
            }
        }
        
        //(6) 按顺序输出元素
        foreach (bond ghj in LINE)
            Console.WriteLine("BFS:" + ghj.id);
    }

}

class bond
{
    public int id;//节点的id
    public int[] nbs;//用于存储该元素的临接元素的id
    public bool visited = false;//是否被遍历过的标记，默认false表示没有被遍历过
    public List<bond> GET_NBS(List<bond> ttt)
    {
        //用于获得当前元素的邻接节点集合
        List<bond> NBS = new List<bond>();
        foreach (int qq in this.nbs)
            NBS.Add(ttt.FirstOrDefault(k => k.id == qq));
        return NBS;
    }
}