mainul098
4/11/2017 - 4:40 AM

Depth First Search

Depth First Search

using System.Collections.Generic;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var grpah = new Graph();
            grpah.AddEdge(0,1);
            grpah.AddEdge(0,2);
            grpah.AddEdge(2,3);
            grpah.AddEdge(3,1);
            grpah.AddEdge(1,3);
            grpah.DepthFirstSearch();
        }
    }

    class Graph{
        private HashSet<int> vertices;
        private IDictionary<int,HashSet<int>> adjacencyList;

        private HashSet<int> visited;

        public Graph()
        {
            this.vertices = new HashSet<int>();
            this.adjacencyList = new Dictionary<int,HashSet<int>>();
        }

        public void AddEdge(int u, int v){
            this.vertices.Add(u);
            this.vertices.Add(v);
            if (!this.adjacencyList.ContainsKey(u)){
                this.adjacencyList.Add(u, new HashSet<int>());
            }
            this.adjacencyList[u].Add(v);

            if (!this.adjacencyList.ContainsKey(v)){
                this.adjacencyList.Add(v, new HashSet<int>());
            }
            this.adjacencyList[v].Add(u);
        }

        public void DepthFirstSearch(){
            var astronaut = new List<int>();
            int prev = 0;
            foreach(var v in this.vertices){
                if(!this.visited.Contains(v)){
                    this.DepthFirstSearchVisit(v);
                    astronaut.Add(this.visited.Count - prev);
                    prev = this.visited.Count;
                }
            }
        }

        private void DepthFirstSearchVisit(int s)
        {
            var stack = new Stack<int>();
            stack.Push(s);
            while(stack.Count != 0){
                var vertex = stack.Pop();
                if(!visited.Contains(vertex)){
                    foreach(var v in this.adjacencyList[vertex]){
                        if(!this.visited.Contains(v))
                        {
                            stack.Push(v);
                        }
                    }
                }
            }
        }
    }
}