क्लोन ग्राफ (LeetCode 133): पायथन में हैश मैप के साथ DFS

Clone Graph (LeetCode 133) में आपको एक connected undirected graph की deep copy return करनी होती है। मुख्य विचार है हर original node से उसके copy तक जाने वाला hash map। इससे आप हर copy एक ही बार बनाते हैं और cycles पर हमेशा के लिए loop किए बिना neighbors को जोड़ देते हैं। Time और space O(V + E) हैं।

समस्या

आपको एक connected undirected graph के एक node का reference मिलता है। हर node की एक value और neighbors की एक list होती है। एक deep copy return करें: समान values और समान connections वाले नए nodes, और original के साथ कोई node साझा न हो। Input None भी हो सकता है, उस स्थिति में None return करें।

Node class ऐसा दिखता है:

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

यह सिर्फ़ recursion क्यों नहीं है

एक graph में cycles हो सकते हैं, और undirected graph में हर edge एक छोटा cycle होता है (A में B है, और B में A)। ऐसा copy function जो हर neighbor पर खुद को call करता है, कभी रुकेगा नहीं। आपको याद रखना होगा कि कौन-से nodes पहले ही copy हो चुके हैं।

तरीका: map और depth-first search

एक dictionary copies रखें जो हर original node को उसके clone से map करती है। एक stack के साथ graph में चलें। जब आपको ऐसा neighbor मिले जिसे आपने copy नहीं किया है, उसका clone बनाएँ और उसे push करें। किसी भी तरह, neighbor के clone को current clone की neighbor list में जोड़ दें।

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

Trace

एक square graph लें, 1, 2 और 4 से जुड़ा है, 2, 3 से, 3, 4 से। Node 1 से शुरू करें: copy 1 बनाएँ, फिर node 1 के neighbors 2 और 4 पर जाएँ, दोनों के copies बनाएँ और उन्हें copy 1 से जोड़ें। Node 4 pop करें: इसके neighbors 1 और 3 हैं, तो copy 1 जुड़ जाता है (पहले से मौजूद है), और copy 3 बनाकर जोड़ दिया जाता है। Node 3, फिर node 2 pop करें, और बाकी links जुड़ जाते हैं। हर node एक बार बनता है, और हर edge दोनों दिशाओं में दिखता है, क्योंकि हर endpoint दूसरे को अपनी list में जोड़ता है।

Depth-first या breadth-first

दोनों काम करते हैं। Breadth-first के लिए stack को deque और popleft() से बदल दें। एकमात्र ज़रूरत map है। Recursion लिखने में छोटा होता है, लेकिन गहरा graph Python की recursion limit तक पहुँच सकता है, इसलिए iterative version ज़्यादा सुरक्षित है।

आम गलतियाँ

• हर बार node दिखने पर नया clone बनाना, जिससे nodes duplicate हो जाते हैं और loop कभी खत्म नहीं होता।
• Neighbor list को reference से copy करना, जिससे clone वापस original nodes की ओर इशारा करता है।
• None input भूल जाना।
• Node value को map key की तरह इस्तेमाल करना जब values के unique होने की गारंटी न हो। Node object खुद इस्तेमाल करना ज़्यादा सुरक्षित है।

Test करने के लिए edge cases

Interview में इसे कैसे समझाएँ

1. बताएँ कि यहाँ deep copy का क्या मतलब है: नए nodes, वही shape।
2. Cycles की ओर इशारा करें और बताएँ कि map क्यों चाहिए।
3. Original से clone तक के map, और traversal का वर्णन करें।
4. इसे लिखें, फिर दो-node वाले उदाहरण से चलकर दिखाएँ।
5. O(V + E) time और O(V) space बताएँ।

मैंने publish करने से पहले ऊपर दिए गए code को 3,000 random connected graphs पर test किया, यह जाँचते हुए कि copy में वही values और edges हैं और original के साथ कोई node साझा नहीं है। ऐसा त्वरित random check अभ्यास करते समय एक अच्छी आदत है।

संबंधित अभ्यास

Complexity की शब्दावली के लिए हमारी Big O cheat sheet देखें, आगे क्या अभ्यास करें इसके लिए LeetCode Blind 75 list, और अभ्यास कैसे करें इसके लिए coding interview assistant guide देखें।

कोड करते समय अपना तरीका ज़ोर से बोलकर समझाएँ। एक transcript दिखाता है कि आपने लिखने से पहले मुख्य observation बताया या नहीं। किसी भी live assessment में AI tools पर employer के नियमों का पालन करें।