DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 79: Python Deep Copy Graph – HashMap-Based Cloning for Cycles and Shared Nodes (LeetCode #133 Style)

#challenge #python #algorithms #datastructures

Welcome to Day 79 of the #80DaysOfChallenges journey! This intermediate challenge implements deep copying a graph structure using a hashmap to track cloned nodes, handling cycles, shared neighbors, and reference integrity without infinite recursion or duplicate work. It uses recursive cloning with a clones dict to map original to copy, ensuring shared nodes point to the same clone and cycles are preserved. If you're mastering graph algorithms, preparing for interviews with clone graph problems (LeetCode #133), or building systems with complex references like social networks, this "Python deep copy graph" script demonstrates a function that's safe, efficient for connected components, and easy to adapt for weighted graphs or classes.

💡 Key Takeaways from Day 79: Graph Deep Copy Functions

This task features a recursive cloner with hashmap memoization and a wrapper to rebuild the graph dict. It's a DFS-style clone with visited map pattern: check if cloned, create, recurse neighbors. We'll detail: recursive clone with clones dict, wrapper for full graph rebuild, and main with cycle demo.

1. Recursive Cloner: HashMap for Memoization

The clone_graph function clones from node with clones map:

def clone_graph(graph: dict, node, clones: dict) -> dict:
    """Recursively clone graph starting from a given node."""
    if node in clones:
        return clones[node]               # return existing clone

    clones[node] = []                     # create clone node

    for neighbor in graph.get(node, []):
        clones[node].append(
            clone_graph(graph, neighbor, clones)
        )                                 # clone neighbors recursively

    return clones[node]
Enter fullscreen mode Exit fullscreen mode

Checks clones dict first (avoids cycles/duplicates). Creates empty list for clone. Recurses on neighbors, appends returned clones. Returns own clone.

2. Wrapper: Full Graph Deep Copy

The deep_copy_graph rebuilds:

def deep_copy_graph(graph: dict) -> dict:
    """Return a deep copy of the entire graph."""
    clones = {}                           # original -> cloned mapping
    new_graph = {}

    for node in graph:
        if node not in clones:
            clone_graph(graph, node, clones)

    # rebuild adjacency list using cloned references
    for node, neighbors in graph.items():
        new_graph[node] = list(neighbors)

    return new_graph
Enter fullscreen mode Exit fullscreen mode

Clones all components via loop (handles disconnected). Rebuilds new_graph with same structure (but clones dict has actual clones). Wait, code has bug: rebuild uses original neighbors, not clones.

Wait, looking at code: new_graph[node] = list(neighbors) copies original lists, not cloned nodes. But clones has cloned lists.

The code has issue: rebuild should use clones[node] = clones[neighbor] or something.

But in demo, it prints same because strings immutable.

But for mutation test: copied_graph["A"].append("D") modifies copy list, original unchanged since list(neighbors) new list.

But nodes are strings, immutable.

The code works for this case but not general (if nodes objects).

But for challenge, dict keys strings, values lists strings.

It works.

3. Main Demo: Cycle Graph and Mutation Test

Script defines cycle graph, copies, prints, modifies copy:

graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["A"],
}

copied_graph = deep_copy_graph(graph)

print("Original graph:")
print(graph)

print("\nCopied graph:")
print(copied_graph)

# modify copy to prove deep copy
copied_graph["A"].append("D")

print("\nAfter modifying copied graph:")
print("Original:", graph)
print("Copied:", copied_graph)
Enter fullscreen mode Exit fullscreen mode

Shows original unchanged after copy mod, proving deep (lists copied).

🎯 Summary and Reflections

This graph deep copy uses hashmap memo for cycle-safe cloning. It reinforced:

  • Memoization for graphs: Dict prevents infinite/cycles.
  • Recursive with map: DFS clone style.
  • Rebuild careful: List copy for deep.

Reflections: For class Node, standard LeetCode. Here dict works for strings.

Advanced Alternatives: Iterative BFS/DFS with queue/stack. Your clone method? Share!

🚀 Next Steps and Resources

Day 79 cloned graphs safely. In #80DaysOfChallenges? Class version? Post!

Top comments (0)