Grafı kopyalama

Problem

Bağlı, yönsüz bir grafın bir düğümüne referans veriliyor. Her düğüm bir tamsayı değeri ve komşu düğümlerin listesini tutuyor. Grafın derin kopyasını oluşturup kopyadaki karşılık gelen düğümü döndür. Kopyada hiçbir düğüm orijinal grafla paylaşılmamalı; ama kopyanın yapısı (kim kimin komşusu) birebir aynı olmalı.

Orijinal:  1 --- 2
           |     |
           4 --- 3

Komşuluk: 1:[2,4]  2:[1,3]  3:[2,4]  4:[3,1]

Çıktı: aynı komşuluk yapısına sahip 4 YENİ düğüm; 1'in kopyası döner.

Girdi: null        -> null
Girdi: tek düğüm 7, komşusu yok -> komşusu olmayan yeni bir 7

Netleştirme soruları

• Graf yönsüz ve bağlı mı? (Evet; yönlü ya da bağlantısız olsaydı sadece başlangıçtan ulaşılabilen kısım kopyalanabilir.)
• Döngü ve kendine kenar (self-loop) olabilir mi? (Döngü kesin var; self-loop'u sormak iyi bir detay.)
• Düğüm değerleri benzersiz mi? (LeetCode'da evet, ama çözüm buna güvenmemeli: harita anahtarı değer değil düğüm referansı olmalı.)
• Komşu sırası korunmalı mı?
• Graf ne kadar büyük; derinlik özyineleme için sorun olur mu?

İpuçları

Yaklaşım

Saf (yanlış) yaklaşım: Her düğüm için new Node(val) oluşturup komşularını özyinelemeli kopyalamak. Döngülü grafta sonsuza girer; döngü olmasa bile ortak komşular birden fazla kez kopyalanır ve yapı bozulur (paylaşılan düğüm iki ayrı düğüme dönüşür).

Harita ile dolaşım (optimal): Kopyalama aslında bir graf dolaşımıdır; ek olarak Map<Node, Node> tutulur. Harita iki işe yarar: (1) her orijinal düğüm için tam olarak bir kopya oluşturulmasını garanti eder, (2) ziyaret kümesi görevi görür. Kenarlar, bir düğüm kuyruktan çıktığında kopyalar arasında kurulur.

BFS ya da DFS fark etmez. Özyinelemeli DFS kısadır:

clone(node):
  if node in map: return map[node]
  copy = new Node(node.val); map[node] = copy   // komşulardan ÖNCE haritaya koy
  for n in node.neighbors: copy.neighbors.add(clone(n))
  return copy

Kritik ayrıntı: kopya, komşuları dolaşmadan önce haritaya konmalıdır; aksi halde döngüde aynı düğüme geri dönüldüğünde harita boş bulunur ve sonsuz özyineleme başlar. Aşağıdaki çözüm iteratif BFS kullanır.

Java çözümü

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class CloneGraph {

    static final class Node {
        final int val;
        final List<Node> neighbors = new ArrayList<>();
        Node(int val) { this.val = val; }
    }

    public Node cloneGraph(Node start) {
        if (start == null) return null;

        Map<Node, Node> copies = new HashMap<>();       // orijinal -> kopya; aynı zamanda "ziyaret edildi"
        copies.put(start, new Node(start.val));
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Node original = queue.poll();
            Node copy = copies.get(original);
            for (Node neighbor : original.neighbors) {
                Node neighborCopy = copies.get(neighbor);
                if (neighborCopy == null) {               // ilk kez görüldü: kopyala ve kuyruğa al
                    neighborCopy = new Node(neighbor.val);
                    copies.put(neighbor, neighborCopy);
                    queue.offer(neighbor);
                }
                copy.neighbors.add(neighborCopy);         // kenarı kopyalar arasında kur
            }
        }
        return copies.get(start);
    }
}

Harita anahtarı Node'dur ve Node equals/hashCode'u override etmediği için kimlik karşılaştırması yapılır; bu tam istenen davranıştır. Değeri anahtar yapmak (Map<Integer, Node>) LeetCode'da çalışır ama değerler benzersiz değilse yanlış olur. Node'a yapısal equals eklenirse kimlik semantiğini korumak için IdentityHashMap kullanılmalıdır.

Karmaşıklık

• Zaman: O(V + E). Her düğüm bir kez kopyalanır ve kuyruğa girer; her kenar her iki uçtan birer kez işlenir.
• Bellek: O(V) harita ve kuyruk (çıktı hariç).

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• null girdi: null.
• Komşusuz tek düğüm: yeni nesne, aynı değer, boş komşu listesi.
• 4 düğümlü kare: değer bazlı komşuluk listeleri (sıra dahil) birebir aynı; orijinal ve kopya düğüm kümeleri arasında hiçbir ortak referans yok (IdentityHashMap tabanlı kümeyle kontrol edildi).
• Kendine kenarlı düğüm: kopyanın komşusu kopyanın kendisi.
• 300 rastgele bağlı graf (1-20 düğüm, ek rastgele kenarlar): yapı aynı, ortak referans yok.

"Ortak referans yok" testi bu sorunun özüdür; sadece değerleri karşılaştıran bir test, orijinal düğümleri döndüren hatalı bir çözümü de geçirir.

Mülakatçı için

Adayın derin kopya ile sığ kopya farkını ve döngülerin neden harita gerektirdiğini açıklayabilmesi beklenir. Java geliştiricisi için doğal bir bağlantı noktası: clone() ve kopya constructor'larında da aynı problem vardır (döngüsel referanslı nesne grafları). Jackson gibi serileştiriciler döngüsel referansta @JsonIdentityInfo gibi kimlik bazlı mekanizmalar kullanır.

İpucu zamanlaması: Aday harita fikrine 5 dakikada ulaşamazsa ilk ipucunu ver, çünkü sorunun tamamı bu fikre dayanır. Özyinelemeli DFS yazan adayda "haritaya ne zaman koyuyorsun?" sorusunu özellikle sor; komşulardan sonra koyan aday döngüde sonsuz özyinelemeye girer.

Takip sorusu 1: Her düğümde next ve rastgele bir random işaretçisi olan bağlı listeyi kopyala. Beklenen: aynı harita fikri (O(n) bellek) ya da kopyaları orijinallerin arasına serpiştirip O(1) ek bellekle çözmek (LeetCode 138).

Takip sorusu 2: Graf bağlantısız ve elinde tüm düğümlerin listesi var. Beklenen: aynı haritayı paylaşarak her ziyaret edilmemiş düğümden dolaşım başlatmak.

Takip sorusu 3: Bu graf bir JPA entity grafı (sipariş, kalemler, ürünler; çift yönlü ilişkiler). Bir siparişi "kopyalayıp yeni taslak oluştur" özelliğini nasıl yazarsın? Beklenen: hangi ilişkilerin derin (kalemler) hangilerinin sığ (ürün referansı) kopyalanacağına karar vermek, ID'leri sıfırlamak, çift yönlü ilişkilerde iki tarafı da kurmak ve lazy yükleme sırasında N+1 sorgu riskine dikkat etmek.

Benzer problemler

• Copy List with Random Pointer (LeetCode 138)
• Clone Binary Tree With Random Pointer (LeetCode 1485)
• Clone N-ary Tree (LeetCode 1490)
• Course Schedule (LeetCode 207)
• Number of Islands (LeetCode 200)