NUHMAN.com

Introduction

LeetCode 133: Clone Graph is a problem where the goal is to clone or deep copy an undirected graph. The graph is represented by nodes where each node contains a value and a list of neighbors. You need to create a deep copy of the graph such that the structure of the new graph is the same, but the nodes are distinct from the original graph.

Problem Statement

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains:

• val: an integer representing the node's value.
• neighbors: a list of neighboring nodes.

You need to create a clone of the graph, where each node's value and its neighbors are exactly replicated, but the nodes are distinct from the original.

Example:

go

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation:

In the given example, the graph consists of four nodes. The nodes are connected as follows:

• Node 1 is connected to Node 2 and Node 4.
• Node 2 is connected to Node 1 and Node 3.
• Node 3 is connected to Node 2 and Node 4.
• Node 4 is connected to Node 1 and Node 3.

The output is a deep copy of this graph, where each node’s value and neighbors are copied, but the nodes themselves are new instances.

Approach:

Depth-First Search (DFS) Approach

To clone the graph, we can use a Depth-First Search (DFS) approach to traverse through all the nodes and their neighbors, creating a new node for each original node and establishing the same connections.

1. Recursive DFS:

• If a node has already been visited, we return the clone of that node (avoid cycles and re-cloning).
• For each unvisited node, create a new clone, then recursively visit all its neighbors.

1. HashMap for Node Mapping:

• Use a map (hashmap) to store the mapping between the original nodes and their clones to ensure that each node is cloned only once.

1. Base Case:

• If the node is nil (i.e., the graph is empty), return nil.

Go Implementation

Solution Using DFS

go

package main

import "fmt"

// Definition for a Node.
type Node struct {
    Val       int
    Neighbors []*Node
}

// DFS function to clone the graph
func cloneGraph(node *Node, visited map[*Node]*Node) *Node {
    if node == nil {
        return nil
    }

    // If the node is already visited, return its clone from the visited map
    if clone, found := visited[node]; found {
        return clone
    }

    // Create a new clone of the current node
    clone := &Node{Val: node.Val}
    visited[node] = clone

    // Clone all the neighbors recursively
    for _, neighbor := range node.Neighbors {
        clone.Neighbors = append(clone.Neighbors, cloneGraph(neighbor, visited))
    }

    return clone
}

// Main function to clone the graph
func cloneGraphMain(node *Node) *Node {
    visited := make(map[*Node]*Node)
    return cloneGraph(node, visited)
}

// Helper function to print graph (for testing purposes)
func printGraph(node *Node) {
    visited := make(map[*Node]bool)
    var dfs func(n *Node)
    dfs = func(n *Node) {
        if n == nil || visited[n] {
            return
        }
        visited[n] = true
        fmt.Printf("Node %d: ", n.Val)
        for _, neighbor := range n.Neighbors {
            fmt.Printf("%d ", neighbor.Val)
        }
        fmt.Println()
        for _, neighbor := range n.Neighbors {
            dfs(neighbor)
        }
    }
    dfs(node)
}

func main() {
    // Create sample graph: Node 1 -> Node 2, Node 4; Node 2 -> Node 1, Node 3; etc.
    node1 := &Node{Val: 1}
    node2 := &Node{Val: 2}
    node3 := &Node{Val: 3}
    node4 := &Node{Val: 4}

    node1.Neighbors = []*Node{node2, node4}
    node2.Neighbors = []*Node{node1, node3}
    node3.Neighbors = []*Node{node2, node4}
    node4.Neighbors = []*Node{node1, node3}

    // Clone the graph
    clonedGraph := cloneGraphMain(node1)

    // Print the original and cloned graphs to verify
    fmt.Println("Original Graph:")
    printGraph(node1)

    fmt.Println("\nCloned Graph:")
    printGraph(clonedGraph)
}

Explanation:

1. Node Struct:

• The Node struct is defined to represent each graph node, which contains a value (Val) and a list of neighbors (Neighbors).

1. cloneGraph Function:

• This is the recursive DFS function that clones each node. It checks if a node has been visited using a map (visited) and if so, returns its clone from the map.
• If the node hasn’t been visited, a new clone is created, and the function recurses through its neighbors.

1. cloneGraphMain Function:

• This is the main function that starts the DFS cloning process and returns the deep copy of the graph.

1. printGraph Function:

• A helper function that uses DFS to print out the graph for verification.

1. Main Function:

• In the main function, we create a simple graph, clone it using cloneGraphMain, and print both the original and cloned graphs for validation.

Time and Space Complexity

MetricComplexityTime ComplexityO(V + E)Space ComplexityO(V)

Time Complexity:

• O(V + E) where V is the number of nodes and E is the number of edges. Each node is visited once, and for each node, we iterate over all its neighbors.

Space Complexity:

• O(V) where V is the number of nodes in the graph. The space is used to store the visited map and the new nodes being created (clone of the graph).

Edge Cases

1. Empty Graph:

• Input: nil (empty graph)
• Output: nil
• Explanation: If the input graph is empty, the function should return nil.

1. Single Node:

• Input: 1 -> nil (single node with no neighbors)
• Output: 1 -> nil
• Explanation: If the graph consists of a single node with no neighbors, the clone should be the same single node with no neighbors.

1. Cyclic Graph:

• Input: A graph with cycles (e.g., node 1 -> node 2 -> node 3 -> node 1)
• Output: A deep copy of the graph, maintaining the cycle.
• Explanation: The algorithm ensures that cycles are handled properly by using the visited map.

Conclusion

LeetCode 133: Clone Graph is a problem that can be effectively solved using Depth-First Search (DFS) with backtracking. By utilizing a hashmap to store cloned nodes and recursively cloning each node and its neighbors, the problem can be solved in a time-efficient manner. This solution provides an excellent example of using DFS for graph traversal and deep copying of graph structures.