Graph Breadth First Search

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

namespace Graph
{
    class BFS
    {
        private List<int>[] graph_childnodes;

        public BFS(int size)
        {
            this.graph_childnodes = new List<int>[size];
            for(int i=1;i<=size;i++)
            {
                graph_childnodes[i] = new List<int>();

            }
        }

        public BFS(List<int>[] childNode)
        {
            graph_childnodes = childNode;

        }


        public int Size
        {
            get { return this.graph_childnodes.Length; }
        }

        public void AddEdge(int u,int v)
        {
            graph_childnodes[u].Add(v);
        }

        public void RemoveEdge(int u, int v)
        {
            graph_childnodes[u].Remove(v);

        }

        public bool HasEdge(int u, int v)
        {
            bool hasEdge = graph_childnodes[u].Contains(v);
            return hasEdge;
        }

        public IList<int> GetSuccessors(int u)
        {
            return graph_childnodes[u];

        }
       
    }

    class graphComponent
    {

        static BFS graph = new BFS(new List<int>[]{
            new List<int>{1,2,3},
            new List<int>{0,4,5},
            new List<int>{0,5},
            new List<int>{0},
            new List<int>{1},
            new List<int>{1,2}
           
        });


       

        static bool[] visited = new bool[graph.Size+1];

        static Queue<int> queue = new Queue<int>();
        static void TraverseBFS(int v)
        {
            queue.Enqueue(v);
            Console.WriteLine(v + " ");
            visited[v] = true;
            while (queue.Count() != 0)
            {
                    int node=queue.Dequeue();
                    foreach (int child in graph.GetSuccessors(node))
                    {
                        if (!visited[child])
                        {
                            visited[child] = true;
                            Console.WriteLine(child + " ");
                            queue.Enqueue(child);
                        }
                       
                    }

               

            }
        }

        static void Main(string[] args)
        {

            List<char> A = new List<char>();
            A.Add('B');
            A.Add('C');
            A.Add('D');

            List<char> B = new List<char>();
            B.Add('A');
            B.Add('E');
            B.Add('F');


            List<char>[] graph1 = new List<char>[5];
            graph1[0] = A;
            graph1[1] = B;

           

            Console.WriteLine("Connected graph components");
            for (int v = 0; v < graph.Size; v++)
            {
                if (!visited[v])
                {
                    TraverseBFS(v);
                    Console.WriteLine();

                }
            }

            Console.ReadLine();
        }
       

    }


}

Comments

Popular posts from this blog

Authentication and Authorization in Web API -Part1

My Gardening Journey 6