enum VertexColor { White, Gray, Black }

    class DepthFirstSearchHelper<T>
    {
        private Vertex<T> _root;
        private readonly List<T> _discovered = new List<T>();
        private readonly Dictionary<Vertex<T>, VertexColor> _verticesColor = new Dictionary<Vertex<T>, VertexColor>();
        private readonly Graph<T> _graph;

        public DepthFirstSearchHelper(Graph<T> graph, Vertex<T> rootVertex = null)
        {
            _graph = graph;
            _root = rootVertex ?? graph.Vertices.First();
        }

        public List<T> Search()
        {
            _discovered.Clear();
            _verticesColor.Clear();

            // mark all vertices white
            foreach (var v in _graph.Vertices)
            {
                _verticesColor[v] = VertexColor.White;
            }

            // visit the root
            Visit(_root);

            // check the adjacent edges now
            foreach (var v in _root.Edges)
            {
                if (_verticesColor[v] == VertexColor.White)
                {
                    Visit(v);
                }
            }
            while (_verticesColor.Values.Contains(VertexColor.White))
            {
                _root = _verticesColor.FirstOrDefault(x => x.Value == VertexColor.White).Key;
                Visit(_root);
            }
            return _discovered;
        }

        private void Visit(Vertex<T> vertex)
        {
            _verticesColor[vertex] = VertexColor.Gray;
            _discovered.Add(vertex.Value);

            foreach (var v in vertex.Edges)
            {
                if (_verticesColor[v] == VertexColor.White)
                {
                    Visit(v);
                }
            }
            _verticesColor[vertex] = VertexColor.Black;
        }
    }