採用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("
");

//(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;

}

}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！