Given a reference of a node in a connected undirected graph. Create a clone of the graph.

Approach: Use DFS with hash (node value as key and graph node as value). In case of DFS we do not traverse the node if it is already visited and here we do the same return the node from the hash.

        public GraphNode CloneGraph(GraphNode node)

        {

            if (node == null)

            {

                return null;

            }

            // Assuming every node has unique value.

            Dictionary<int, GraphNode> visited = new Dictionary<int, GraphNode>();

            return this.CloneGraph(node, visited);

        }

        private GraphNode CloneGraph(GraphNode sourceNode, Dictionary<int, GraphNode> visited)

        {

            if (visited.ContainsKey(sourceNode.Value))

            {

                return visited[sourceNode.Value];

            }

            GraphNode destNode = new GraphNode(sourceNode.Value, new List<GraphNode>());

            visited[sourceNode.Value] = destNode;

            foreach (GraphNode node in sourceNode.Neighbors)

            {

                destNode.Neighbors.Add(this.CloneGraph(node, visited));

            }

            return destNode;

        }