Array: 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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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:

/** * 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; LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>(); UndirectedGraphNode newHead = new UndirectedGraphNode(node.label); queue.add(node); map.put(node, newHead); while(!queue.isEmpty()){ UndirectedGraphNode cur = queue.pop(); ArrayList<UndirectedGraphNode> currNeighbors = cur.neighbors; for(UndirectedGraphNode u:currNeighbors ){ if(map.containsKey(u)){ map.get(cur).neighbors.add(map.get(u));//add neighbors node }else{ UndirectedGraphNode copy = new UndirectedGraphNode(u.label); map.put(u,copy); map.get(cur).neighbors.add(copy); queue.add(u); } } } return newHead; } }

mistakes: queue should existing node.

learned: 1)queue is used to do breath first traversal. 2)map is used to store the visited nodes. It is the map between original node and copied node.

//dfs solution

public class Solution {

    Map<UndirectedGraphNode, UndirectedGraphNode> visited = null;

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        // Note: The Solution object is instantiated only once and is reused by each test case.

        if(node == null){

return null;

        }

visited = new HashMap<UndirectedGraphNode, UndirectedGraphNode> ();

return cloneG(node);

    }

public UndirectedGraphNode cloneG(UndirectedGraphNode node){

        if(node == null){

return node;

        }

        if(visited.containsKey(node)){

return visited.get(node);

        }

UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        visited.put(node, newNode);

        for(UndirectedGraphNode neighbor: node.neighbors){

            newNode.neighbors.add(cloneG(neighbor));

        }

return newNode;

    }

}

//

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; // the mapping between each original node and the copy node HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); HashSet<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>(); UndirectedGraphNode first = new UndirectedGraphNode(node.label); map.put(node, first); set.add(node); // Traverse the original graph in a BFS manner LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); for (UndirectedGraphNode neighbor : node.neighbors) { queue.add(neighbor); } // copy all the labels, and construct the hash map and the hash set while (!queue.isEmpty()) { UndirectedGraphNode neighbor = queue.poll(); set.add(neighbor); if (!map.containsKey(neighbor)) { UndirectedGraphNode copy = new UndirectedGraphNode( neighbor.label); map.put(neighbor, copy); for (UndirectedGraphNode n : neighbor.neighbors) { if (!map.containsKey(n)) queue.add(n); } } } // copy all the neighbors for (UndirectedGraphNode n : set) { UndirectedGraphNode copy = map.get(n); for (UndirectedGraphNode neighbor : n.neighbors) { copy.neighbors.add(map.get(neighbor)); } } return first; }