그래프 이동 Vs 트리 탐색

Question

그래프를 통과하는 함수가 트리를 통과하는 데 똑같이 잘 작동합니까?

Answer 1

글쎄 나무는 방향성이있는 비정상 그래프 라 불리는 특별한 유형의 그래프입니다. 그렇습니다. 넓이 우선과 깊이 첫 번째 탐색은 모두 나무에서 작동합니다.

너비와 깊이의 차이에 대한 자세한 설명을 작성할 수는 있지만 잘못 입력 한 것일 수 있습니다.

너비와 깊이 우선 탐색의 유일한 차이점은 정점을 처리하는 순서입니다. 처음에는 "처리 할"큐에 정점을 추가하는 것으로 생각할 수 있습니다. 우선 깊이는 "처리 될 스택"에 정점을 추가하는 것으로 생각할 수 있습니다. 정점을 처리 할 시간이 왔을 때 (각 데이터 구조에 추가 된 후에) 다음 정점을 처리하기 위해 스택에서 대기열을 제거하거나 팝합니다. 영리한 버전의 깊이 우선 탐색은 스택에 추가하는 대신 정점을 처리하기 위해 재귀를 사용합니다.

나는이 도움이 아닌지 여부 아무 생각 ...이 없다

빠른 구글 검색의 차이점을 설명 꽤 잘 보인다 this을 찾아 (나는 그것이 폭과 깊이를 먼저인지 모른다) BFS 및 DFS. 더 깊이 읽으려면 Steve Skiena의 The Algorithm Design Manual을 추천 할 수도 있습니다.

Answer 2

일반 트리를 탐색 할 수있는 함수는 트리를 탐색 할 때 과도 할 수 있습니다. 순수 트리에서는주기를 확인할 필요가 없기 때문입니다. 그렇게하면 효과가 있지만 더 간단 할 것입니다.