데이터 구조-Breadth First Traversal

BFS (Breadth First Search) 알고리즘은 폭이 넓은 모션으로 그래프를 순회하고, 반복에서 막 다른 골목이 발생할 때 검색을 시작하기 위해 다음 정점을 가져 오는 것을 기억하기 위해 대기열을 사용합니다.

위에 주어진 예에서와 같이 BFS 알고리즘은 먼저 A에서 B, E, F를 거쳐 C로, 마지막으로 G에서 D로 순회합니다. 다음 규칙을 사용합니다.

• Rule 1− 방문하지 않은 인접한 정점을 방문합니다. 방문한 것으로 표시하십시오. 그것을 표시하십시오. 대기열에 삽입하십시오.

• Rule 2 − 인접한 정점이 없으면 대기열에서 첫 번째 정점을 제거합니다.

• Rule 3 − 대기열이 비워 질 때까지 규칙 1과 규칙 2를 반복합니다.

단계	순회	기술
1		대기열을 초기화합니다.
2		우리는 방문에서 시작합니다 S (시작 노드), 방문한 것으로 표시합니다.
삼		그런 다음 방문하지 않은 인접 노드를 S. 이 예에서는 3 개의 노드가 있지만 알파벳순으로 선택합니다.A, 방문한 것으로 표시하고 대기열에 넣습니다.
4		다음으로, 방문하지 않은 인접 노드 S 이다 B. 방문한 것으로 표시하고 대기열에 넣습니다.
5		다음으로, 방문하지 않은 인접 노드 S 이다 C. 방문한 것으로 표시하고 대기열에 넣습니다.
6		지금, S방문하지 않은 인접 노드가 없습니다. 그래서 우리는 대기열에서 빼고A.
7		에서 A 우리는 D방문하지 않은 인접 노드로. 방문한 것으로 표시하고 대기열에 넣습니다.

이 단계에서는 표시되지 않은 (방문하지 않은) 노드가 없습니다. 그러나 알고리즘에 따라 우리는 방문하지 않은 모든 노드를 얻기 위해 대기열에서 계속 제거합니다. 대기열이 비워지면 프로그램이 종료됩니다.

이 알고리즘의 C 프로그래밍 언어 구현은 여기에서 볼 수 있습니다 .