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 node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
Code (Java):
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); // create the new node UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); map.put(node, newNode); queue.offer(node); while (!queue.isEmpty()) { UndirectedGraphNode curr = queue.poll(); List<UndirectedGraphNode> neighborNodes = curr.neighbors; for (UndirectedGraphNode neighbor : neighborNodes) { if (!map.containsKey(neighbor)) { UndirectedGraphNode copy = new UndirectedGraphNode(neighbor.label); map.put(neighbor, copy); map.get(curr).neighbors.add(copy); queue.offer(neighbor); } else { map.get(curr).neighbors.add(map.get(neighbor)); } } } return newNode; } }
Update on 9/18/15:
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>(); Queue<UndirectedGraphNode> queue = new LinkedList<>(); queue.offer(node); map.put(node, newNode); while (!queue.isEmpty()) { UndirectedGraphNode curr = queue.poll(); List<UndirectedGraphNode> neighbors = curr.neighbors; for (UndirectedGraphNode neighbor : neighbors) { if (!map.containsKey(neighbor)) { UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label); map.put(neighbor, newNeighbor); map.get(curr).neighbors.add(newNeighbor); queue.offer(neighbor); } else { UndirectedGraphNode newNeighbor = map.get(neighbor); map.get(curr).neighbors.add(newNeighbor); } } } return newNode; } }
/** * Definition for Undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { * label = x; * neighbors = new ArrayList<UndirectedGraphNode>(); * } * } */ public class Solution { /** * @param node: A undirected graph node * @return: A undirected graph node */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { // write your code here if (node == null) { return null; } Map<UndirectedGraphNode, UndirectedGraphNode> nodeMap = new HashMap<>(); // step 1: clone the vertex Queue<UndirectedGraphNode> queue = new LinkedList<>(); Set<UndirectedGraphNode> set = new HashSet<>(); queue.offer(node); while (!queue.isEmpty()) { UndirectedGraphNode currNode = queue.poll(); // copy the vertex nodeMap.put(currNode, new UndirectedGraphNode(currNode.label)); for (UndirectedGraphNode neighbor : currNode.neighbors) { if (!nodeMap.containsKey(neighbor)) { queue.offer(neighbor); } } } // step 2: copy the edges for (UndirectedGraphNode originalNode : nodeMap.keySet()) { for (UndirectedGraphNode neighbor : originalNode.neighbors) { nodeMap.get(originalNode).neighbors.add(nodeMap.get(neighbor)); } } return nodeMap.get(node); } }
What would be the time complexity?
ReplyDelete