[BFS] 너비 우선 탐색
너비우선탐색(BFS) 이란?그래프를 완전탐색하는 방법 중 하나로,시작 노드에서 시작해 가장 가까운 노드를 먼저 탐색하면서 탐색하는 알고리즘FIFO 구조로 탐색을 하며, 목표 노드에 도착하는 경로가 여러개 일 경우 최단경로를 보장한다.시간복잡도 O(노드 수 + 에지 수)로 이루어져 있다. 너비우선탐색의 핵심이론DFS와 마찬가지로 방문한 노드의 경우 체크하는 배열이 필요.또한, 인접 리스트를 구현하여 에지로 구성되어있는 배열을 구현해야함DFS와 다른점이 있다면, 스택으로 제거하는 것이 아닌 큐의 형태로 먼저 들어온 순서부터 제거하며 삽입 및 삭제를 진행.과정첫번째 노드부터 큐에 삽입하여, 큐를 시작하고 인접해 있는 노드를 차례대로 큐에 삽입한다큐에 먼저 들어간 노드부터 삭제하며, 인접한 노드들이 있다면 차례..
알고리즘
2024. 11. 18. 15:08
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- JDBC
- 타입변환
- 버블정렬
- Java
- bean
- JSON
- 우선순위 큐
- 예외처리
- 코딩테스트
- Spring
- SQL
- 게시판 프로젝트
- 깊이우선탐색
- 오블완
- 백준
- 포트폴리오
- 게시판
- DFS
- 이진탐색
- 정렬
- Thymeleaf
- 기술면접
- db
- HTML5
- stack
- BFS
- 티스토리챌린지
- 알고리즘
- 검증
- 클래스
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
글 보관함