133.clone-graph.md

133. Clone Graph

Breakdowns

1. Given a single node, how to deep copy?

Just return a new node with the same value.

2. Given a graph with single neighbor (1 -> 2 -> 3), how to deep copy?

We can use DFS or BFS without considering the cycle. (without hash table)

3. What if 3 has a neighbor 1 (form a cycle)?

It's this problem.

DFS + Hash Table

We can use DFS or BFS to traverse from starting node to clone the node, and update the neighbors of the new node by traversing the neighbors of the old node.

We must ensure each node is cloned only once, so we use a hash table (old -> new) to avoid duplicate cloning and infinite loops.

// old: new
// 1: 1'
// 2: 2'
private val map = HashMap<Node, Node>()

fun cloneGraph(node: Node?): Node? {
    if (node == null) return null
    if (node in map) return map[node]
    val newNode = Node(node.`val`)
    map[node] = newNode
    node.neighbors.forEach { adj ->
        newNode.neighbors.add(cloneGraph(adj))
    }
    return newNode
}

// Or equivalently, we check if the node is cloned before we clone the node for the neighbors.
fun cloneGraph(node: Node?): Node? {
    if (node == null) return null
    val newNode = Node(node.`val`)
    map[node] = newNode
    for (adj in node.neighbors) {
        if (adj == null) continue
        if (adj in map) {
            newNode.neighbors.add(map[adj]!!)
        } else {
            newNode.neighbors.add(cloneGraph(adj))
        }
    }
    return newNode
}

// Or equivalently, we can clone the node first and update the neighbors later.
fun cloneGraph(node: Node?): Node? {
    cloneNode(node)
    updateNeighbors(node, HashSet<Node>())
    return map[node]
}

private fun cloneNode(node: Node?) {
    if (node == null || node in map) return
    val newNode = Node(node.`val`)
    map[node] = newNode
    node.neighbors.forEach { adj -> 
        cloneNode(adj)
    }
}

// 1 -> 1'
// 1: [2, 3] -> 1': [2', 3']
private fun updateNeighbors(node: Node?, visited: HashSet<Node>) {
    if (node == null || node in visited) return
    visited.add(node)
    val newNode = map[node]
    node.neighbors.forEach { adj ->
        val adjNew = map[adj]
        newNode?.neighbors?.add(adjNew)
        updateNeighbors(adj, visited)
    }
}    

• Time Complexity: O(n) for DFS traversal.
• Space Complexity: O(n) for hash table and recursion stack.

BFS + Hash Table

In BFS, we clone the source node and enqueue the source node.

Then we clone the neighbors when popping the node from the queue, and also update the neighbors of the new node. The neighbor nodes may or may not be cloned, so we have to check if the node is cloned or not.

A - B
|   
C 

pop A
    A - B // existed, not cloned
      - C // not cloned yet, clone and update the neighbors

For example, A is the node popped from the queue, then we clone B and C, and update the neighbors of A' to [B', C'], we also enqueue B and C to the queue if they are not cloned.

In this approach, we still need old and new node mapping to prevent duplicate visited. We have to update the neighbors of current node when we traverse the neighbors of the old node.

fun bfs(node: Node?): Node? {
    if (node == null) return null
    val queue = ArrayDeque<Node>()
    queue.addLast(node)
    val newNode = Node(node.`val`)
    map[node] = newNode

    while (queue.isNotEmpty()) {
        val old = queue.removeFirst()

        // We don't clone here, we clone and update the neighbors when we visit the adjacent nodes.

        for (adj in old.neighbors) {
            if (adj == null) continue
            if (adj in map) {
                // We have cloned the node, we just update the neighbors.
                map[old]?.neighbors?.add(map[adj])
            } else {
                val newNode = Node(adj.`val`)
                map[adj] = newNode
                map[old]?.neighbors?.add(newNode)
                queue.addLast(adj)
            }
        }
    }
    return newNode
}

• Time Complexity: O(n) for BFS traversal.
• Space Complexity: O(n) for hash table and queue.