Clone Graph - BFS

• don't forget to check when input is null

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        //validate input
        if (node == null) return null;

        Map<Integer, UndirectedGraphNode> map = new HashMap<>();//<label, newNode>

        Queue<UndirectedGraphNode> queue = new LinkedList<>();//next original nodes to be visited
        queue.offer(node);

        while (!queue.isEmpty()) {
            UndirectedGraphNode graphNode = queue.poll();

            if (!map.containsKey(graphNode.label)) {
                map.put(graphNode.label, new UndirectedGraphNode(graphNode.label));
            }

            for (UndirectedGraphNode neighbor : graphNode.neighbors) {
                if (!map.containsKey(neighbor.label)) {
                    map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));
                    queue.offer(neighbor);
                }
                map.get(graphNode.label).neighbors.add(map.get(neighbor.label));
            }
        }
        return map.get(node.label);
    }
}

Clone graph - DFS

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<Integer, UndirectedGraphNode> map = new HashMap<>();//<label, newNode>

        return cloneGraph(node, map);
    }

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
        //exit
        if (node == null) return null;
        if (map.containsKey(node.label)) return map.get(node.label);

        if (!map.containsKey(node.label)) {
            map.put(node.label, new UndirectedGraphNode(node.label));
        }

        for (UndirectedGraphNode neighbor : node.neighbors) {
            map.get(node.label).neighbors.add(cloneGraph(neighbor, map));
        }

        return map.get(node.label);
    }
}

Follow up - what if the labels are not uniquely given to nodes

/**
 * 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 node;
        //a map for old and new nodes
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

        List<UndirectedGraphNode> nodeList = getNodes(node);

        //create a copy for each
        for(UndirectedGraphNode cur : nodeList){
            map.put(cur, new UndirectedGraphNode(cur.label));
        }

        //add neighbors
        for(UndirectedGraphNode cur : nodeList){
            UndirectedGraphNode copy = map.get(cur);

            for(UndirectedGraphNode neighbor : cur.neighbors){
                copy.neighbors.add(map.get(neighbor));
            }
        }

        return map.get(node);
    }

    //visits all nodes and store in a list.
    private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node){
        Set<UndirectedGraphNode> visited = new HashSet<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();

        queue.offer(node);
        visited.add(node);

        while(!queue.isEmpty()){
            UndirectedGraphNode cur = queue.poll();
            for(UndirectedGraphNode next : cur.neighbors){
                if(!visited.contains(next)){
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }

        return new ArrayList<>(visited);
    }
}