Clone Graph

Question

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains alabel (int) and a list (List[UndirectedGraphNode]) of itsneighbors. There is an edge between the given node and each of the nodes in its neighbors.

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

How we serialize an undirected graph:

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

Have you met this question in a real interview? Yes

Example
return a deep copied graph.

Tags

Analysis

Wikipedia:
“In graph theory, breadth-first search (BFS) is a strategy for searching in a graph
when search is limited to essentially two operations: (a) visit and
inspect a node of a graph; (b) gain access to visit the nodes that
neighbor the currently visited node. The BFS begins at a root node and
inspects all the neighboring nodes. Then for each of those neighbor
nodes in turn, it inspects their neighbor nodes which were unvisited,
and so on. Compare BFS with the equivalent, but more memory-efficient
Iterative deepening depth-first search and contrast with depth-first search.”

Depth-first Search

Wikipedia:
“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible
along each branch before backtracking.”

Solution

BFS - breadth first search, non-recursive

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     ArrayList<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) {
if (node == null) {
return null;
}
HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode head = new UndirectedGraphNode(node.label);

while (!queue.isEmpty()) {
UndirectedGraphNode currentNode = queue.remove();
for (UndirectedGraphNode neighbor : currentNode.neighbors) {
if (!hm.containsKey(neighbor)) {
UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
hm.put(neighbor, newNeighbor);
}
}
}

}
}

DFS - depth first search, non-recursive

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     ArrayList<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) {
if(node == null)
return null;

HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode head = new UndirectedGraphNode(node.label);
stack.push(node);

while(!stack.isEmpty()){
UndirectedGraphNode curnode = stack.pop();
for(UndirectedGraphNode aneighbor: curnode.neighbors){//check each neighbor
if(!hm.containsKey(aneighbor)){//if not visited,then push to stack
stack.push(aneighbor);
UndirectedGraphNode newneighbor = new UndirectedGraphNode(aneighbor.label);
hm.put(aneighbor, newneighbor);
}

}
}

}
}

DFS Recursive

public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
return cloneGraph(node, new HashMap<>());
}

private UndirectedGraphNode cloneGraph(UndirectedGraphNode node,
Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap) {

UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
cloneMap.put(node, clone);

for (UndirectedGraphNode neighbor : node.neighbors) {
UndirectedGraphNode neighborClone = cloneMap.get(neighbor);
if (neighborClone != null) {
}
else {