Take the 2-minute tour ×

Algorithm to clone a tree is quite easy, we can do pre-order traversal for that. Is there an efficient algorithm to clone a graph?

I tried a similar approach, and concluded we need to maintain a hash-map of nodes already added in the new graph, else there will be duplication of nodes, since one node can have many parents.

share|improve this question
modified bfs/dfs where nodes are copied when they are marked as "visited" ? –  Oren Jan 26 '13 at 12:00
Depends heavily on the data-structure. –  Zeta Jan 26 '13 at 12:11
Graph traversal on wikipedia. Relatively big article that might give you something. –  ᴋᴇʏsᴇʀ Jan 26 '13 at 12:17
@Zeta Assuming graph is represented as Adjacency Matrix –  Amit Jan 26 '13 at 12:29
@Keyser DFS/BFS with flag in original graph will help me to not visit the node again. But in the new graph i do want a link between the current node and a node already added in the graph. Since the already added node has more than one parents. Think of it as some social network graph where in you will have mutual friends. –  Amit Jan 26 '13 at 12:32
show 1 more comment

3 Answers

It suffices to do a depth first search and copy each node as it's visited. As you say, you need some way of mapping nodes in the original graph to corresponding copies so that copies of cycle edges can be connected correctly.

This map also suffices to remember nodes already visited in the DFS.

So in Java you'd have something like:

class Node {

  // Contents of node...
  Data data;

  // ... member declarations like array of adjacent nodes
  final ArrayList<Node> children = new ArrayList<>();

  // Recursive graph walker for copying, not called by others.
  private Node deepCloneImpl(Map<Node, Node> copies) {
    Node copy = copies.get(this);
    if (copy == null) {
      copy = new Node(data);
      // Map the new node _before_ copying children.
      copies.put(this, copy);
      for (Node child : children)
    return copy;

  public Node deepClone() {
    return deepCloneImpl(new HashMap<Node, Node>());

A different approach is to put an additional field in each node that points to the copy if there is one and is null otherwise. This merely implements the map by another method. But it requires two passes over the graph: one to make the copy and another to clear these map fields for future re-use.

share|improve this answer
add comment

Your hash map approach seems viable if you had some quick way of uniquely identifying every node.

Otherwise, you would be best off if you:

  1. used data-structure to store graph that allows you to store "is duplicated" unique flag directly in every node (for example, 0 not duplicated, 1 to numberOfNodes for duplicated nodes),

  2. traversed nodes (via BFS, DFS) taking care of the already duplicated nodes and reconstructing all connections from the starting graph.

Both your starting graph and finishing graph should have corresponding unique "is duplicated" flag in every node, so you are able to reconstruct connections from starting graph properly. Of course, you could use "is duplicated" flag and "unique identifier" as separate variables.

share|improve this answer
add comment

As you copy nodes from the source graph, place each node in a <Node, Integer> map (thus numbering the nodes from 1 to N).

As you paste nodes in the destination graph, place each node in a <Integer, Node> map (again numbering from 1 to N, but with mapping in reverse direction for reasons that will be clear soon).

When you find a backlink in the source graph, you can map that backlinked "source copy" node to an integer i using the first map. Next, you use the second map to lookup the integer i and find the "destination copy" node which needs to have the same backlink created.

share|improve this answer
I just realized this is pretty much the same answer Gene posted above, but with the Node<->Node map exploded into two maps. Oh well. :-) –  The111 Aug 10 '13 at 0:24
add comment

Your Answer


