BFS
2023. 10. 29. 11:51ㆍ컴퓨터/알고리즘
반응형
그래프를 순회하는 방법 BFS (Breadth First Search) 는 너비 우선 탐색이다.
이러한 그래프가 있으면
쭉 들어가는 DFS와 달리 인접한 Vertex에 모두 방문.
대충 이런식이다!
BFS는 인접한 Vertex에 방문하는 형식이라서 길찾기 알고리즘에 쓰인다고 한다.
DFS를 코드로 구현해본다면
이러하다.
Queue 에 인접한 Vertex를 넣어서(예약해서)
다음 반복때 예약된 번호를 빼고 다시 인접한 Vertex를 예약하고.. Queue의 요소가 0이 될때까지 반복한다!
Queue는 선입 선출의 자료구조라 먼저 예약된 Vertex가 먼저 나올것!
parent와 distance라는 개념을 도입하면, 내가 어느 Vertex에서 왔는지, 내가 시작 위치보다 얼마만큼의 거리를 왔는지 볼 수 있다.
이런 요소들이 바로 길찾기 알고리즘에 사용됨!
'컴퓨터 > 알고리즘' 카테고리의 다른 글
| BFS를 이용한 길찾기 (0) | 2023.10.29 |
|---|---|
| DFS (0) | 2023.10.28 |
| 알고리즘 공부 1 (0) | 2023.10.26 |