반응형
BFS 랑 DFS의 차이점은 BFS는 큐를 , DFS는 스택을 이용한 다는 차이 밖에 없다
또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프[2][3]에서는' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다.
dfs 는??
[실전 알고리즘] 0x05강 - BFS, DFS_구버전
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 현재 보고있는 강..
blog.encrypted.gg
반응형
'알고리즘' 카테고리의 다른 글
| 다이나믹 프로그래밍(Dynamic Programming) : 동적 계획법 (0) | 2020.04.19 |
|---|---|
| 투 포인터(Two Pointers) (0) | 2020.04.18 |
| 플러드 필(Flood Fill) - BFS , DFS (0) | 2020.04.18 |
| 최단 경로 문제 : 플로이드-워셜 알고리즘 (0) | 2020.04.18 |
| Hash Table (0) | 2020.04.05 |
댓글