Deep Copy graph with possible circle

思路：

hash map stores <Original, Copy> to avoid duplicate

expand the V, and generate its neighbors to copy the relationship , each time to expand or generate copy, need to check whether it already in the hashtable

Solution 1 (DFS + HashMap)

public class Solution {

public class Solution {

    public List<GraphNode> copy(List<GraphNode> graph) {

        // Write your solution here.
        if (graph == null) {
            return null;
        }
        //it could have isolated node, use BFS better

        Map<GraphNode,GraphNode> map = new HashMap<GraphNode, GraphNode>();
        for (GraphNode node : graph) {
        if (!map.containsKey(node)) {
        // expand the V and use DFS method generate its neighbors
        map.put(node,new GraphNode(node.key));
        dfs(node,map);
        }
    }

    return new ArrayList(map.values());
}

private void dfs(GraphNode node, Map<GraphNode,GraphNode> map) {

    GraphNode copyNode = map.get(node);

    // copy its neighbors
    for(GraphNode neighbor : node.neighbors) {
        if (!map.containsKey(neighbor)) {
            map.put(neighbor, new GraphNode(neighbor.key));
            dfs(neighbor,map);
        }
        copyNode.neighbors.add(map.get(neighbor));
    }
}
}

Solution 2 Iteratively

// copy the V node and copy its neighbors , each time of copy need to check hash table

/
*

* class GraphNode {

* public int key;

* public List<GraphNode> neighbors;

* public GraphNode(int key) {

* this.key = key;

* this.neighbors = new ArrayList<GraphNode>();

* }

* }

*/

public class Solution {

    public List<GraphNode> copy(List<GraphNode> graph) {
        // Write your solution here.
        if (graph == null) {
        return null;
        }

        //it could have isolated node, use BFS better
        Map<GraphNode,GraphNode> map = new HashMap<GraphNode, GraphNode>();
        for (GraphNode node : graph) {
            if (!map.containsKey(node)) {
            map.put(node,new GraphNode(node.key));
            }

            GraphNode copyNode = map.get(node);
            for(GraphNode nei : node.neighbors) {
                if(!map.containsKey(nei)) {
                    map.put(nei,new GraphNode(nei.key));
                }

                copyNode.neighbors.add(map.get(nei));

            }

        }

        return new ArrayList(map.values());

    }

}

Solution 3 Recursive

* public List<GraphNode> neighbors;

* public GraphNode(int key) {

* this.key = key;

* this.neighbors = new ArrayList<GraphNode>();

* }

* }

*/

public class Solution {

    public List<GraphNode> copy(List<GraphNode> graph) {

        // Write your solution here.
        if (graph == null) {
            return null;
        }

        //it could have isolated node, use BFS better
        Map<GraphNode,GraphNode> map = new HashMap<GraphNode, GraphNode>();
        for (GraphNode node : graph) {
            cloneGraph(node,map);
        }

        return new ArrayList(map.values());
    }


    private GraphNode cloneGraph(GraphNode node, Map<GraphNode,GraphNode> map) {

        if (node == null) {
        //base case
        return node;
        }

        if (map.containsKey(node)) {
        return map.get(node);
        }

        GraphNode copyNode = new GraphNode(node.key);
        map.put(node,copyNode);
        for(GraphNode nei : node.neighbors) {
            copyNode.neighbors.add(cloneGraph(nei,map));
        }

        return copyNode;
    }
}