DepthFirst Traversal of a graph in C#


DepthFirst Traversal of a graph in C#
For understanding graphs in c# Please go through the below tutorial

http://www.introprogramming.info/tag/graph-implementation/#_Toc362296541

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

namespace Graph
{
    class Graph
    {

        private List<int>[] childnodes;

        public Graph(int size)
        {
            this.childnodes = new List<int>[size];
            for (int i = 0; i < size; i++)
            {
                this.childnodes[i] = new List<int>();
            }
        }


        public Graph(List<int>[] childnode)
        {
            this.childnodes = childnode;
        }


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

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


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

        }

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

        public IList<int> GetSuccessors(int v)
        {
            return childnodes[v];
        }

    }


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

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

        static void TraverseDFS(int v)
        {
            if (!visited[v])
            {
                Console.Write(v + " ");
                visited[v] = true;
                foreach (int child in graph.GetSuccessors(v))
                {
                    TraverseDFS(child);
                }

            }

        }


        static void Main(string[] args)
        {
            Console.WriteLine("Connected graph components");
            for (int v = 0; v < graph.Size; v++)
            {
                if (!visited[v])
                {
                    TraverseDFS(v);
                    Console.WriteLine();

                }
            }

            Console.ReadLine();
        }
    }
}

Comments

Popular posts from this blog

Authentication and Authorization in Web API -Part1

My Gardening Journey 6