CareerCup

Well it depends on the representation of your graph, like in which way are you trying to represent it - Matrix form or list form. Copying via list form will always take less space.

There may be other ways for copying it, for example. you can write list representation in a text file like this :

1 : 2,3,4
2 : 1,5
4 : 3,5

i.e. 1st node has an edge from 1 to 2,3 and 4. 2nd has edge from 2 to 1 and 5 etc.

You can read above text file while creating graph.

dfs?

We can do it using one queue, and using BFS approach.
Pseudo code-

Node start_node = getRandomStartNode(set_of_vertices);

Queue q <= empty_queue;
q.add(start_node);

Graph duplicate_graph <= new Graph();

while(q not empty)
	Node hop = q.remove();
	for( Vertex v in Adjacent_Vertices_Set(hop) )
		duplicate_graph.add(hop, v);
		q.add(v);

The best way to optimize space and avoid problems with cycles is having a reference to the nodes of the new graph. It can also be done using a data structure like a Hashmap but it wastes more memory.

public Node copyGraph(Node root){
	Node next = root;
	int size = 0;
	while(next != null && next.copy == null){
		next.copy = new Node();
		next = next.next;
		size++;
	}

	next = root;
	Node copyNext = root.copy;
	while(size > 0){
		if(next.next != null)
			copyNext.next = next.next.copy;
		next = next.next;
		copyNext = copyNext.next;
		size--;
	}

	next = root;
	while(next.copy != null){
		next.copy = null;
		next = next.next;
	}

}