DFS 알고리즘 순회

Question

은 스택과 DFS 탐색 내게 folowing 경로를 제공 ...

1-2-3-4-5-6

인가 위의 경로는 유효합니까? 다른 경로가 있습니까? (내 교과서는 저에게 1-2-3-6-4-5를 제공합니다)

컴퓨터 과학 스택에 이미지를 게시 할 수있는 충분한 담당자가 없기 때문에 여기에 묻기 만하면됩니다. ; 그렇지 않으면 나중에 삭제 해 드리겠습니다. 당신은 그래프의 완벽하게 유효한 DFS 통과를 나와 있고, 교과서는 당신에게 그래프의 또 다른 완전히 합법적 인 DFS 통과를주고있다

Answer 1

감사합니다. 같은 그래프의 깊이 우선 탐색 (deep-first traversal)이 많이있을 수 있습니다 (실제로는 지수 적으로 많은 그래프가 있습니다). 따라서 교과서와 같은 것을 얻지 못하면 즉각적인 경보 원인이 아닙니다. 에 대한 몇 가지 다른 규칙이있는 경우 어떻게 노드가 그 다음, DFS를 (예를 들어, 항상 오름차순 또는 내림차순으로 연결된 노드를 방문) 방문되어야한다,

1 2 5 4 3 6 
3 1 6 2 5 4 
5 4 2 3 1 6 
... 

그러나 다음은

는 다른 순서 부입니다 검색은 항상 동일한 출력을 생성합니다.

희망이 도움이됩니다.

Answer 2

설명하는 출력은 경로가 아니며 DFS가 노드를 방문하는 순서입니다. 경로는 각 노드가 이전 및 다음 노드에 연결된 노드 목록입니다.

는 DFS 탐색의 출력은 또한 귀하의 경우에 해당하는 DFS 탐색 트리로 볼 수있다

:

이

1 - 2 - 3 - 4 - 5 
     | 
     6 

교과서 트리

1 - 2 - 3 - 6 
     | 
     4 - 5 

당신은 다른 많은 얻을 수있다 DFS 트리는 선택의 여지가있는 지점에서 가장 먼저 이동할 위치를 결정할 수 있기 때문에 가능합니다. 예에서 노드 3에서 노드 4 또는 노드 6으로 이동할 수 있으며 다른 출력은 다른 선택 사항 때문입니다.