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

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


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



답변

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

그래프를 고려하십시오

여기에 이미지 설명을 입력하십시오

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

A,B,E,C,D

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

A,B,E,D,C

Θ(V+E)

O(V)

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


답변