Check if path exists between two nodes in a graph using Breadth first search (BFS)

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);

            node r6 = new node(6);

            r0.children = new node[] { r1, r4, r5 };
            r1.children = new node[] { r3 };
            r3.children = new node[] { r2 };
            r2.children = new node[] { r1 };
            Console.WriteLine(isPathExistsBFS(r1, r2));
     
        }
     
        public static bool isPathExistsBFS(node start, node end)
        {
            if (start == end)
            {
                return true;
            }
            Queue<node> q = new Queue<node>();
            start.isVisited = true;
            q.Enqueue(start);
           
            while (q.Count > 0)
            {
                var nQ = q.Dequeue();

                if (nQ.children != null)
                {
                    foreach (var n in nQ.children)
                    {
                        if (n.isVisited == false)
                        {
                            n.isVisited = true;
                            q.Enqueue(n);
                            if (n == end)
                            {
                                return true;
                            }

                        }
                    }
                }
            }
            return false;
        }   
    }
 
    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