C# 廣度優先搜索

 

 

廣度優先搜索是一種用於圖的查找算法,它主要解決兩個問題:

1.從節點S到節點E有路徑嗎?

2.從節點S到節點E的所有路線中,哪條最短?

廣度優先搜索的執行過程中，搜索範圍從起點開始逐漸向外延伸，即先檢查一度關係，再檢查二度關係.

所謂一度關係:我的朋友和我就是一度關係.

所謂二度關係:我的朋友的朋友和我就是二度關係.

以此類推.

曾經不知道在哪裡看到過一句話:

解決問題,先確定數據結構,數據結構確定好了,算法自然而然就出來了.不過我覺得我離這個境界還有點遠….

那麼圖應該用哪種數據結構表示呢?

因為一個節點可以指向多個節點,當然,也可以不指向任何節點.所以我們可以用散列表: Dictionary<T,List<T>> (也許還有其他方式,但是小弟確實不懂,只懂這個)

由於多個節點可以指向同一個節點,自己也可以指向自己,所以在搜索的過程中,對於檢查過的節點,我們不能再去檢查,否則可能會導致無限循環,因此我們需要一個數據結構來保存搜索過的節點,這個用 List<T> 或者 HashSet<T> 都可以.

前面說到了,該算法搜索的時候是從內到外,一層一層搜索,最裏面一層搜索完了,遞增一層繼續搜索,逐漸向外延伸.

那麼這裡肯定需要一種數據結構來存儲需要檢查的節點.

同時,由於是從內到外,層層遞增搜索,所有這裡就有個先後順序的問題了.那就是必須要把第一層的節點搜索完,才能搜索第2層,第2層的節點搜索完,才能搜索第3層.像這種有先後順序要求的數據結構,必須隊列:Queue<T>,我們將需要搜索的節點放到隊列中,比如:

起點S的第1層關係中有2個節點:A和B,我們先把這兩個節點插入隊列.那麼這個插入有順序要求嗎?沒有!同一層的節點插入到隊列的順序不重要,因為該算法計算的是最短距離,不是最快距離.

假設順序是A,B,我們先檢查A,如果A不是我們要找的終點(假設是E),那麼我們就把A指向的所有節點插入到隊列,插入到隊列後,它們是排在B的後面,所以只有等第1層的B檢查完了,才會檢查它們.當B檢查完了,也不是我們要找的終點,我們再把B指向的所有節點插入到隊列,這也就實現了1層1層的遞增檢查.

 

通過上面的方法,我們可以解決開篇提到的第1個問題:從S到E是否有路徑.但是無法解決第2個問題:最短路徑是哪條.

要解決這個問題,在搜索的過程中就必須保存當前搜索的節點是從哪個節點過來的.因為前面也提到了,在圖這種數據結構中,多個節點是可以指向同一個節點的.並且一個節點也是可以指向多個節點的,所以我們必須清楚的知道,當前搜索的節點是從哪個節點(哪條線路)過來的.

打個不太恰當的比方:

5+5=10

但是10!=5+5 ,10還可以==1+9,==2+8,==3+7 ……

所以,前面提到的,創建一個隊列來保存需要檢查的節點是不行的,我們還需要保存節點的父節點,因為我們需要知道我們是怎麼來的!

因此,我封裝了一下當前節點類型,提供了一個屬性來保存它的父親.

(這個設計可能不太好,額外空間可能耗得比較多,小弟暫時沒想到什麼好的辦法)

 

代碼如下:

 

    public class Route<T>
    {
        /// <summary>
        /// 終點相對於起點的維度
        /// </summary>
        public int Dimension { get; }

        /// <summary>
        /// 完整路線
        /// </summary>
        public string FullRoute { get; }

        public Route(Stack<T> stack)
        {
            FullRoute = string.Join(",", stack);
            Dimension = stack.Count - 1;
        }
    }

 

    public class RouteNode<T>
    {
        public T Value { get; }
        public RouteNode<T> Parent { get; set; }

        public RouteNode(T value)
        {
            Value = value;
        }

        public Route<T> Route
        {
            get
            {
                var stack = new Stack<T>();
                stack.Push(this.Value);
                var parent = Parent;
                while (parent != null)
                {
                    stack.Push(parent.Value);
                    parent = parent.Parent;
                }
                Route<T> route = new Route<T>(stack);
                return route;
            }
        }
    }

 

    public class MyGraph<T> where T : IComparable<T>
    {
        //節點集合
        private readonly Dictionary<T, IList<T>> _nodes;

        public MyGraph() : this(new Dictionary<T, IList<T>>())
        {

        }

        public MyGraph(Dictionary<T, IList<T>> nodes)
        {
            _nodes = nodes;
        }

        public void Add(T key, IList<T> value)
        {
            _nodes.Add(key, value);
        }

        /// <summary>
        /// 判斷是否有從 start 到 end 的路徑
        /// </summary>
        /// <param name="start">開始點</param>
        /// <param name="end">結束點</param>
        /// <param name="route">路線</param>
        /// <returns></returns>
        public bool TryFindMinRoute(T start, T end, out Route<T> route)
        {
            route = null;
            if (_nodes.TryGetValue(start, out var nodes) == false)
            {
                throw new Exception("not find the element:" + start);
            }
            if (nodes == null || nodes.Count == 0)
            {
                return false;
            }
            //已搜索元素的集合
            var searched = new HashSet<T>();
            //將要搜索的節點隊列
            var searching = new Queue<RouteNode<T>>();
            foreach (var item in nodes)
            {
                searching.Enqueue(new RouteNode<T>(item)
                {
                    Parent = new RouteNode<T>(start),
                });
            }

            while (searching.Count > 0)
            {
                RouteNode<T> node = searching.Dequeue();

                //判斷當前元素是否搜索過,避免無限循環.
                if (searched.Contains(node.Value))
                {
                    continue;
                }

                if (node.Value.CompareTo(end) == 0)
                {
                    route = node.Route;
                    return true;
                }

                searched.Add(node.Value);

                if (_nodes.TryGetValue(node.Value, out var forwardNodes) == false || forwardNodes == null || forwardNodes.Count == 0)
                {
                    //說明 當前元素 沒有指向任何元素
                    continue;
                }

                foreach (var item in forwardNodes.Where(item => searched.Contains(item) == false))
                {
                    searching.Enqueue(new RouteNode<T>(item)
                    {
                        Parent = node
                    });
                }
            }
            return false;
        }
    }

 

Test:

            MyGraph<string> dic = new MyGraph<string>();
            dic.Add("start", new List<string> { "bob", "alice", "claire" });
            dic.Add("bob", new List<string> { "anuj", "dandan1" });
            dic.Add("alice", new List<string> { "peggy" });
            dic.Add("claire", new List<string> { "thom", "jonny" });
            dic.Add("anuj", new List<string>() { "wahaha", "dandan2" });
            dic.Add("dandan2", new List<string>() { "wahaha", "claire" });
            dic.Add("peggy", new List<string>() { "gongwei" });
            dic.Add("gongwei", new List<string>() { "jonny" });
            dic.Add("thom", new List<string>());
            dic.Add("jonny", new List<string> { "refuge" });
            dic.Add("wjire", new List<string>());
            dic.Add("refuge", new List<string>() { "dandan", "bob" });
            var r = dic.TryFindMinRoute("alice", "claire", out var route);
            if (r)
            {
                Console.WriteLine($"在第{route.Dimension}層找到:" + route.FullRoute);
            }
            else
            {
                Console.WriteLine(r);
            }

 

Tags:

VirMach 便宜 VPS

QNews

QNews