경계 깊이 우선 검색이란 무엇입니까

깊이 우선 검색은 개발 파충류 초기에 더 많이 사용하는 방법입니다.

1, 깊이 우선 검색

깊이 우선 검색은 그래프와 트리에 대한 순회 알고리즘으로 DFS (Depth First Search) 로 축약됩니다. 깊이 우선 검색은 그래프 이론의 고전적인 알고리즘으로, 깊이 우선 검색 알고리즘을 사용하여 대상 그래프의 해당 토폴로지 정렬 테이블을 생성할 수 있으며, 토폴로지 정렬 테이블을 사용하면 최단 경로 문제 등과 같은 많은 관련 그래프 문제를 쉽게 해결할 수 있습니다.

일반적으로 힙 데이터 구조를 사용하여 DFS 알고리즘 구현을 지원합니다. 이 프로세스는 가능한 각 분기 경로에 대해 더 이상 드릴 다운할 수 없을 때까지 심층적으로 진행되며 노드당 한 번만 액세스할 수 있습니다.

2, 폭 우선 검색

폭 우선 검색 Dijkstra 단일 소스 최단 경로 알고리즘과 Prim 최소 스패닝 트리 알고리즘 모두 너비 우선 검색과 유사한 아이디어를 사용합니다. BFS 라고도 하는 그 별명은 그림의 모든 노드를 체계적으로 확장하고 검사하여 결과를 찾는 맹목적인 검색 방법입니다.

즉, 결과의 가능한 위치를 고려하지 않고 결과를 찾을 때까지 전체 그림을 철저히 검색합니다. 기본적으로 BFS 는 루트 노드에서 시작하여 트리의 폭을 따라 트리의 노드를 트래버스합니다. 모든 노드가 액세스되면 알고리즘이 중단됩니다. 일반적으로 대기열 데이터 구조를 사용하여 BFS 알고리즘의 구현을 지원합니다.

깊이 우선 순회의 생각:

먼저 그림에 지정된 시작점 ⅵ (ⅵ) 을 방문한 다음 ⅵ (ⅵ

아직 액세스되지 않은 인접 점이 있는 경우 이 정점을 액세스한 후 해당 정점에서 위와 유사한 액세스를 수행합니다. 한 단계 뒤로 돌아간 후 이전 정점에도 액세스되지 않은 인접 점이 없는 경우 한 단계 더 뒤로 돌아가서 검색을 수행하고 모든 정점이 액세스될 때까지 위 절차를 반복합니다.