깊이 우선 순회 및 너비 우선 순회

깊이 우선 탐색

주어진 그래프 G의 초기 상태를 가정합니다. 누구도 방문한 적이 없는 모든 정점입니다. G에서 임의의 정점 v를 초기 시작점(소스 포인트)으로 선택하면 깊이 우선 순회는 다음과 같이 정의될 수 있습니다. 먼저 시작점 v를 방문하고 방문한 것으로 표시한 다음 v에서 시작하여 각 인접 포인트를 검색합니다. v.w. (추천 학습: 웹 프론트 엔드 비디오 튜토리얼)

w가 이전에 방문되지 않은 경우 w는 깊이 우선을 계속하기 위한 새로운 시작점으로 사용됩니다. 그림의 모든 합계 소스까지 순회합니다. v 지점(소스 지점에서 도달할 수 있는 정점이라고도 함)에 연결된 경로가 있는 모든 정점을 방문할 때까지입니다.

이때 그래프에 아직 방문하지 않은 정점이 있다면, 방문하지 않은 다른 정점을 새로운 소스 포인트로 선택하고 그래프의 모든 정점을 방문할 때까지 위 과정을 반복합니다.

그래프의 깊이 우선 순회는 선주문 트리 순회와 유사합니다. 채택된 탐색 방식의 특징은 최대한 깊이 방향으로 먼저 탐색하는 것이다. 이 검색 방법을 깊이 우선 검색이라고 합니다. 따라서 이 방법을 사용하여 그래프를 순회하는 것을 자연스럽게 그래프의 깊이 우선 순회라고 합니다.

직접 말하면 깊이 우선 탐색은 남쪽 벽에 부딪히지 않고 벽에 부딪히지 않는 알고리즘입니다. 경로를 완료한 후 분기된 노드로 돌아가서 계속 탐색합니다.

표시된 바와 같이:

폭 우선 순회#🎜🎜 #

그래프의 정점 V0에서 시작하여 이 정점을 방문합니다.

V0에서 시작하여 V0의 방문하지 않은 인접 점 W1, W2,...,Wk를 방문합니다. ;그런 다음 W1, W2,...,Wk부터 시작하여 방문하지 않은 인접 점을 차례로 방문합니다.

모든 정점을 방문할 때까지 2단계를 반복합니다.

이것은 트리의 레이어 순서 순회와 유사한 레이어별 프로그레시브 알고리즘입니다.

폭 우선 검색 중에는 "레이어별" 확장 방법으로 시작점에서 탐색합니다. 확장하는 동안 포인트가 발견될 때마다 해당 포인트가 대기열에 추가됩니다. 전체 그림이 횡단된 위치가 될 때까지.

위 내용은 깊이 우선 순회 및 너비 우선 순회의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!