그래프를 탐색하는 방법에는 크게 깊이우선탐색(DFS)와 너비우선탐색(BFS)가 있다.
📖그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종이다. 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.
1. 깊이 우선 탐색(DFS, Depth-First Search)
: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
📖 깊이 우선탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.
ex) 미로찾기
구현
- STEP1 : 스택에 시작 노드를 넣는다.
- STEP2 : 스택이 비어있으면 실행을 멈추고 False를 반환함.
- STEP3 : 스택의 맨 위노드가 찾고자 하는 노드이면 탐색을 종료하고 True 반환함.
- STEP4 : STEP3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP하고 스택에 들어 온 적 없는 POP한 노드의 모든 이웃노드를 찾아서 순서대로 스택에 넣는다.
- STEP5 : Step 3로 돌아감.
출처 https://developer-mac.tistory.com/64
DFS 장점
- 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
- 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있따.
DFS 단점
- 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색한다. 효율성을 높이기 위해 미리 지정한 임의 깊이 까지만 탐색하고 해를 발견하지 못하면 다른 경로를 탐색하는 방법을 사용한다.
- DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문이다.
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
2. 너비 우선 탐색(BFS, Breadth-First Search)
:최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
📖너비 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
- 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색
출처 https://developer-mac.tistory.com/64
BFS 장점
- 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
- 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.
BFS 단점
- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
- 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다
DFS VS BFS 탐색 차이
- DFS는 스택(혹은 재귀), BFS 큐를 사용함.
- BFS는 재귀적으로 동작하지 않는다.
BUT문제를 푸는 입장에서는 다음과 같은 구분점 필요
- 최단거리문제를 푼다면 BFS를 사용
- 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋다.
출처 https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
참고
https://devuna.tistory.com/32
https://covenant.tistory.com/132
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
