경로 탐색 알고리즘 - 너비 우선 탐색(BFS, Breadth First Search)

BFS(너비 우선 탐색)

그래프를 탐색할 때,

깊이를 우선해서 탐색하면 깊이 우선 탐색(DFS, Depth First Search),

넓이를 우선해서 탐색하면 너비 우선 탐색(BFS, Breadth First Search)이라고 한다

BFS와 DFS의 차이

참고 사이트

	너비 우선 탐색(BFS)	깊이 우선 탐색(DFS)
사용처	최단 경로 찾기	미궁 자동 생성

BFS의 설계와 구현

인접한 정점(Vertex)에 대한 방문 규칙이 필요하다

그리드 방식에서 인접한 상하좌우를 방문할 것인지, 대각선도 포함할 것인지 등등

 

인접 정점들을 인덱스로 관리하면 셀(배열) 방식

인접 정점들을 리스트로 관리하면 노드 방식

 

어떠한 구조로 되어 있는가 = 자료 구조

어떻게 찾아가는가 = 알고리즘

 

BFS는 최단 거리를 찾을 때 사용될 수 있다

(구현에는 큐를 사용함)

 

방문한 자식 노드들을 큐에 넣고

모든 자식 노드들을 방문했으면

큐에서 맨 앞의 요소를 빼서 그 요소의 자식 노드들을 방문

모든 노드들을 방문할 때까지 반복

 

SSS