Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumgraph-dfs

Clone Graph

Problem (yeniden ifade)

Bağlı, yönsüz bir grafta bir düğüm referansı verildiğinde grafin derin kopyasını döndür. Her düğümün benzersiz bir val’i ve komşu listesi vardır. Döngüler beklenir.

Sezgi

Aynı düğümü iki kez kopyalarsan döngüyü parçalarsın. Orijinal düğümü ilk gördüğünde klonunu ayır ve orijinal → klon kaydet. Kenarları bu haritadan komşu bakarak kopyala. Harita aynı zamanda visited kümesidir.

Yaklaşımlar

DFS + kopya haritası

Doğrulanmadı

Zaman O(V+E)Alan O(V)

Fikir. clones: Map<Node, Node>. Ziyarette: zaten klonlandıysa onu döndür; değilse kopyayı oluştur, komşuları gezmeden önce haritaya koy (geri kenar onu bulsun), sonra dfs(neighbor)’ı copy.neighbors’a ekle.

Yürüyüş. Dört düğümlü döngü 1—2—3—4—1. İlk DFS 1 sonra 2’yi ayırır; 1’e geri kenar haritayı vurur, yeniden ayırmaz.

Trade-off. Doğal graph-DFS. Klonu komşulardan önce ekle; yoksa döngü yığını patlatır / düğüm çoğaltır.

Çözüm

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    const hit = clones.get(n);
    if (hit) return hit;
    const copy = new Node(n.val);
    clones.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    const hit = clones.get(n);
    if (hit) return hit;
    const copy = new Node(n.val);
    clones.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

BFS + kopya haritası

Doğrulanmadı

Zaman O(V+E)Alan O(V)

Fikir. Başlangıcı klonla, kuyruğa al. Çekilen her düğümün her komşusu için: ilk görülüşte klonla ve kuyruğa ekle; klonlanmış komşuyu her zaman klon düğümün listesine ekle.

Yürüyüş. Aynı döngü: BFS 1’i, sonra 1’in komşularından 2 ve 4’ü, sonra 3’ü klonlar; her kenar her yönde bir kez kopyalanır.

Trade-off. Aynı harita değişmezi, açık kuyruk. Uzun yolda özyineleme derinliği korkutuyorsa bunu tercih et. Orijinal düğümü döndürmek (klonlamayı unutmak) aynı komşuluk listesine serileşir — kimlik kontrolleri yakalar.

Çözüm

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>([[node, new Node(node.val)]]);
  const q: Node[] = [node];
  for (let i = 0; i < q.length; i++) {
    const n = q[i]!;
    for (const nb of n.neighbors) {
      if (!clones.has(nb)) {
        clones.set(nb, new Node(nb.val));
        q.push(nb);
      }
      clones.get(n)!.neighbors.push(clones.get(nb)!);
    }
  }
  return clones.get(node)!;
}

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>([[node, new Node(node.val)]]);
  const q: Node[] = [node];
  for (let i = 0; i < q.length; i++) {
    const n = q[i]!;
    for (const nb of n.neighbors) {
      if (!clones.has(nb)) {
        clones.set(nb, new Node(nb.val));
        q.push(nb);
      }
      clones.get(n)!.neighbors.push(clones.get(nb)!);
    }
  }
  return clones.get(node)!;
}

Şablon bağlantısı

Graph DFS’in clone-graph şekli: Map<eski, yeni> artı ziyarette kopyala. Komşuluk listesi komşu sayımıdır; visited klon haritasıdır.

Yansıma

Map eski düğümden klona. Komşu klonda yoksa yarat, varsa yalnızca kenarı bağla. DFS ve BFS aynı grafı üretir.
Döngü map sayesinde ikinci kez klonlanmaz. Giriş null ise null.
Tek düğüm, kendine kenar. Komşusu olmayan düğümün klonunda liste boş.