Graf DFS

Nasıl düşünülür

Graf DFS, visited seti olan ağaç DFS’tir. Grafta parent/child garantisi olmadığından, bir düğümü tekrar ziyaret etmemek için rekürse etmeden önce (veya sırasında) işaretlemen gerekir. İskelet tamamen şudur: işaretle, ziyaret edilmemiş her komşuyu keşfet, rekürse et. Bu kadar. Hemen her graf-DFS problemi bu değişmezin üzerine bir katman ekler (bileşen say, yol takip et, ikili renklendir, back-edge tespit et).

Mülakatlarda iki gösterim baskındır: genel grafklar için komşuluk listesi (Map<V, V[]>) ve flood-fill / ada problemleri için 2D ızgara (int[][] ile 4 yönlü komşular). Şablon aynıdır; yalnızca komşu sayımı değişir.

Şablon şekilleri

Şekil	Temel hamle	Örnek
Bileşen sayma	if !visited: dfs(v); count++	LC 200, LC 547
Flood fill	Hücreyi değiştir, 4 komşuyu dfs	LC 733, LC 695
Grafı klonla	Map<eski, yeni>; dfs + ziyarette kopyala	LC 133
Pacific-Atlantic	Sınırlardan iki DFS, kesişim	LC 417

Karmaşıklık temeli

O(V + E) zaman, visited sayesinde her düğüm ve kenar bir kez işlenir. Alan O(V): visited seti artı rekürsyon derinliği (yol grafağında worst case O(V)). Izgara problemlerinde V → hücreler (RC), E → 4R*C.

Şablondan probleme

1. Gösterimi seç: komşuluk listesi, ızgara veya örtük (ör. kelimeler).
2. “Visited”ın ne anlama geldiğini belir, boolean dizi, set veya ızgarayı yerinde değiştirmek.
3. Her DFS çağrısının döndürdüğü değişmezi tanımla: sayı, boolean ulaşım, klon.
4. Tüm başlangıçları döngüle; ziyaret edilmemiş her başlangıç bir bileşen / bir fill tohumlar.

/** Graph DFS template: count components + flood fill on a grid. */

export function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) { dfs(v); count++; }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]) if (!visited[u]) dfs(u);
  }
}

export function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

/** Graph DFS template: count components + flood fill on a grid. */

export function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) { dfs(v); count++; }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]) if (!visited[u]) dfs(u);
  }
}

export function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}