BFS 구현에서 큐를 스택으로 변경하면 DFS를 얻습니까? by one edge

광범위한 첫 번째 검색을위한 표준 의사 코드는 다음과 같습니다.

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

다음 push과 pop큐 동작으로 간주된다. 그러나 스택 작업 인 경우 어떻게해야합니까? 결과 알고리즘은 깊이 우선 순서로 정점을 방문합니까?

“이것은 사소하다”라는 의견에 투표했다면 왜 사소한 지 설명해달라고 부탁합니다. 문제가 상당히 까다 롭습니다.

답변

아니요, 이것은 DFS와 다릅니다.

그래프를 고려하십시오

노드를 오른쪽에서 왼쪽으로 밀면 알고리즘이 순회를 제공합니다.

A,B,E,C,D

DFS는 그것을 기대할 것이지만

A,B,E,D,C

Θ(V+E)

O(V)

나는 문제가 사소한 것이 아니라고 동의한다.

답변