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 / \ \_/

**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:

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; } }

What would be the time complexity?

ReplyDelete