Depth First-Search는 노드를 어떻게 방문합니까?

Question

알고리즘은 한 노드에 두 번째로 올 수 있습니다. 즉 노드에 두 개의 경로가있을 수 있습니다. 알고리즘은 어떤 경로가 더 짧았는지 알아야합니다.

베스트 퍼스트 검색이 이전에 방문한 노드에 도달하면 이전 방문의 경로가 더 길어질 수 있습니다. 이 경우 열린 목록과 닫힌 목록을 업데이트해야합니다. 이것은 A * 검색에서 발생할 수 없습니다.

질문 : DFS를 사용할 수 있습니까?

대답은 '예'이지만 '아니오'라고 생각했습니다. 왜 그렇습니까? 일단 노드가 방문되면 다시 돌아 가지 않을 것이라고 생각했습니다.

Answer 1

DFS 전략은 노드에 대한 경로를 찾는 횟수만큼 노드를 방문합니다. 해당 노드에서 계속해서 방문하지는 않지만 방문 자체를 등록합니다. 이는 DFS edge classification에 필수입니다.

예를 들어,이 그래프에서 DFS를 실행 해보십시오 : 처음 노드 C에 도달하면

는 경로 A-B-C입니다. 두 번째로 C에 도달하면 경로는 A-C으로 짧아집니다.

Answer 2

이

A 
|\ 
B \ 
| E 
C/
|/ 
D 

같은 그래프가 왼쪽에서 오른쪽으로 깊이 우선, 다음하는 Pathes가 순서대로 방문 할 것이다 그것을 통과 경우 :

당신이 볼

A 
AB 
ABC 
ABCD 
AE 
AED 

, D의 첫 번째 방문은 두 번째 방문 (AED)보다 긴 경로 (ABCD)에 있습니다.