BFS(너비우선탐색)이란

그래프 탐색

하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하는 것

예) 회로에서 특정 단자와 단자가 연결되어있는지

 

BFS을 진행하면 A-B-C-D-E-F-G 순이다.

 

 

너비우선탐색(BFS, Breadth-First Search)

• 임의의 노드에서 시작하여 인접한 노드를 탐색하는 방법.
• 시작 노드에서 부터 가까운 노드를 먼저 방문하고 멀리 떨어진 정점은 나중에 방문하는 순회방법.
• 두 노드사이의 최단경로를 찾아야하거나 임의 경로를 찾고싶을 때 사용.
• 어떤 노드를 방문했는지 반드시 검사해야 한다. 하지 않으면 무한루프에 빠질 수 있다.
• BFS는 차례로 저장하고 꺼낼 수 있는 큐를 사용하여 선입선출 원칙으로 탐색한다.
  BFS는 방문 노드의 인접한 노드를 큐에 저장하는 것이 DFS와 다른 점.

 

 

🔽 REFERENCE

알고리즘 - BFS(너비 우선 탐색)