Breadth first search (BFS) Graphs implementation in C#

Here is the code:
 class Program
    {
        static List<int> li = new List<int>();
        static void Main(string[] args)
        {         
            node r0 = new node(0);

            node r1 = new node(1);
            node r2 = new node(2);
            node r3 = new node(3);
            node r4 = new node(4);
            node r5 = new node(5);

            r0.children = new node[] { r1, r4, r5 };
            r1.children = new node[] { r3 };
            r3.children = new node[] { r2 };
            r2.children = new node[] { r1 };
     
            List<node> li = BFS(r0);
            foreach (var item in li)
            {
                Console.WriteLine(item.data);
            }

        }

        public static List<node> BFS(node r)
        {
            Queue<node> q = new Queue<node>();
            List<node> li = new List<node>();
         
            q.Enqueue(r);
            r.isVisited = true;
            li.Add(r);

            while (q.Count > 0)
            {
                var n = q.Dequeue();
                if (n.children != null)
                {
                    foreach (var _n in n.children)
                    {
                        if (_n.isVisited == false)
                        {
                            _n.isVisited = true;
                            li.Add(_n);
                            q.Enqueue(_n);
                        }
                    }
                }
            }
            return li;
        }
    }
    public class node
    {
        public int data { get; set; }
        public node[] children { get; set; }
        public bool isVisited { get; set; }

        public node(int _data)
        {
            data = _data;
        }
    }

Note:   This Solution is written by me and is not completely tested. Please comment if you found any alternative solutions or any enhancement to my solution.

No comments:

Post a Comment

Popular Posts