Check if path exists between two nodes in a graph using Depth first search (DFS)

Here is the code:

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

namespace ConsoleApplication75
{
    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(isPathExistsDFS(r1, r2));
     
        }
     
        public static bool isPathExistsDFS(node start, node end)
        {
            if (start == end)
            {
                return true;
            }
            start.isVisited = true;
            if (start.children != null)
            {
                foreach (var item in start.children)
                {
                    if (item.isVisited == false)
                    {
                        item.isVisited = true;
                        if (item == end)
                        {
                            return true;
                        }
                        else
                        {
                            return isPathExistsDFS(item, end);
                        }
                    }
                }
            }
         
            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