Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
/
/
0 — 2
/
_/

这道题和copy linked list with random pointer有点类似,我们同样通过遍历原graph来copy和reconstruct新的graph
唯一要做的就是用一个visited的hashmap将已经访问过的node和与其相应的新copy的node保存起来,在重建graph的时候,如果已经visit过,就不需要再copy,只要找到copy中相应的node并将其加入到neighbor中即可。

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    HashMap<UndirectedGraphNode, UndirectedGraphNode> visited = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null)
            return null;
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        clone.neighbors = new ArrayList<UndirectedGraphNode>();
        visited.put(node, clone);
        for(UndirectedGraphNode n : node.neighbors)
        {
            //deal with self loop
            if (n == node)
                clone.neighbors.add(clone);
            else if (!visited.containsKey(n)) // if neigbor node has not been visited
                clone.neighbors.add(cloneGraph(n));
            else // if neighbor node has been visited
                clone.neighbors.add(visited.get(n));
        }
        return clone;
    }
}

Second Submission:

Notice the visited HashMap contains the label number and the new node. (First submission contains the origial Node and the new Node, probably a better solution for conditions when label number is not unique).

2 steps for BFS:
1.Get one original node from the fifo, if it has been copied (exists in the HashMap), get the cloned Node from the map and copy all the neighbors.
2. If the original neighbor has not been copied, create one and put it into the visited HashMap.


/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null)
            return null;
        HashMap<Integer,UndirectedGraphNode> visited = new HashMap<Integer, UndirectedGraphNode>();
        LinkedList<UndirectedGraphNode> fifo = new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode result = null;
        fifo.add(node);
        while(!fifo.isEmpty()) {
            UndirectedGraphNode curr = fifo.removeFirst();
            UndirectedGraphNode newNode = null ;
            if (visited.containsKey(curr.label)) {
                newNode = visited.get(curr.label);
            }
            else {
                newNode = new UndirectedGraphNode(curr.label);
                visited.put(curr.label, newNode);
            }
            
            if (curr == node) 
                result = newNode;
            for(UndirectedGraphNode n : curr.neighbors) {
                if (visited.containsKey(n.label)) {
                    newNode.neighbors.add(visited.get(n.label));   
                }
                else {
                    fifo.add(n);
                    UndirectedGraphNode newNeigbhor = new UndirectedGraphNode(n.label);
                    newNode.neighbors.add(newNeigbhor);
                    visited.put(n.label, newNeigbhor);
                }
            }
        }
        return result;
    }
}

Same idea, copy the vertices using BFS, then BFS again to copy all the edges

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        //BFS copy all the nodes
        LinkedList<UndirectedGraphNode> fifo = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
        if (node == null)
            return null;
        fifo.add(node);
        visited.add(node);
        //copy all the vertices
        while(!fifo.isEmpty()) {
            UndirectedGraphNode curr = fifo.removeFirst();
            UndirectedGraphNode copy = new UndirectedGraphNode(curr.label);
            map.put(curr, copy);
            if (!curr.neighbors.isEmpty())
                for (UndirectedGraphNode n : curr.neighbors) {
                    if (!visited.contains(n)) {
                        fifo.add(n);
                        visited.add(n);
                    }
                }
        }
        visited = new HashSet<UndirectedGraphNode>();
        fifo.add(node);
        visited.add(node);
        //copy all the edges
        while(!fifo.isEmpty()) {
            UndirectedGraphNode curr = fifo.removeFirst();
            UndirectedGraphNode copy = map.get(curr);
            if (!curr.neighbors.isEmpty())
                for (UndirectedGraphNode n : curr.neighbors) {
                    if (!visited.contains(n)) {
                        fifo.add(n);
                        visited.add(n);
                    }
                    copy.neighbors.add(map.get(n));
                }
        }
        return map.get(node);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s