CloneGraphMain.java

public static void main(String[] args) {
    CloneGraph cg = new CloneGraph();

    // construct the example graph
    Node n1 = new Node(1, new ArrayList<>());
    Node n2 = new Node(2, new ArrayList<>());
    Node n3 = new Node(3, new ArrayList<>());
    Node n4 = new Node(4, new ArrayList<>());
    n1.neighbors.addAll(Arrays.asList(new Node[]{n2, n4}));
    n2.neighbors.addAll(Arrays.asList(new Node[]{n3, n3}));
    n3.neighbors.addAll(Arrays.asList(new Node[]{n2, n4}));
    n4.neighbors.addAll(Arrays.asList(new Node[]{n1, n3}));
    // add a self cycle
    n1.neighbors.addAll(Arrays.asList(new Node[]{n1}));

    // expect the same BFS order print out
    Utilities.printGraphBFS(n1);
    Node copiedN1 = cg.cloneGraphBFS(n1);
    Utilities.printGraphBFS(copiedN1);
}

/**
 * print out a graph in BFS node, note it could be a cycle, so it's not really the topological order
 *
 *      1   -----     2
 *      |             |
 *      4   -----     3
 * @param node
 */
public static void printGraphBFS(CloneGraph.Node node) {
    if (node == null) {
        return;
    }

    Set<CloneGraph.Node> visited = new HashSet<>();
    Queue<CloneGraph.Node> queue = new LinkedList<>();
    queue.add(node);
    System.out.println(node.val);
    visited.add(node);

    while (!queue.isEmpty()) {
        CloneGraph.Node cur = queue.poll();
        for (CloneGraph.Node n : cur.neighbors) {
            if (!visited.contains(n)) {
                queue.add(n);
                System.out.println(n.val);
                visited.add(n);
            }
        }
    }
}