DFS (깊이 우선 탐색)

// 재귀 방식
function dfs(graph, node, visited = new Set()) {
  visited.add(node)
  console.log(node)
  graph[node].forEach((neighbor) => {
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited)
  })
}

// 스택 방식
function dfsStack(graph, startNode) {
  const stack = [startNode]
  const visited = new Set()

  while (stack.length > 0) {
    const node = stack.pop()

    if (!visited.has(node)) {
      console.log(node)
      visited.add(node)
      graph[node]
        .slice()
        .reverse()
        .forEach((neighbor) => {
          if (!visited.has(neighbor)) stack.push(neighbor)
        })
    }
  }
}

const graph = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 5],
  3: [1],
  4: [1],
  5: [2],
}
dfs(graph, 0) // 0, 1, 3, 4, 2, 5
#javascript#algorithm#dfs
#344

Fiber 가 렌더링을 쪼갤 수 있는 이유 — 콜 스택 대신 세 포인터

노드마다 child(첫 자식), sibling(다음 형제), return(부모) 세 링크가 걸려 있다. App 의 child 는 Header, Header 의 sibling 은 Main, Main 의 child 는 List, 각자의 return 은 부모다. 규칙은 넷: child 가 있으면 내려가고, root 에 도달하면 끝내고, sibling 이 없으면 return 으로 올라가며 반복하고, sibling 이 있으면 옆으로 간다. 내려가는 길이 beginWork, 올라오는 길이 completeWork 라 한 노드를 두 번 지난다. 순서: begin App → begin Header → complete Header → begin Main → begin List → complete List → complete Main → complete App.

재귀로 순회하면 어디까지 했는지가 JS 콜 스택의 프레임(App → Main → List)에 쌓여 있어, 도중에 양보하려고 함수를 빠져나오면 그 프레임이 풀려나간다. 세 포인터로 순회하면 진행 상태가 workInProgress 포인터 하나로 줄어든다 — 노드마다 걸린 링크를 직접 따라가므로 호출 스택이 필요 없고, 멈추면 그 포인터만 남아 거기서 다시 시작한다.

Footnotes

  1. “Nothing in Fiber uses the normal JS stack.” / 스택을 다시 쌓는 비용보다 중단이 문제다 — “…we would spend some time unwinding and rebuilding the stack each time. It is not too bad. However, everything along the stack would have to be aware of how to “unwind” when we abort in the middle of the work flow.“ 다만 원문도 Fiber 사정이라고 못박는다 — ”…a few unique design patterns that apply to Fiber, but not necessarily anything else.“ ↩

#react#fiber#algorithm#dfs
#560