[알고리즘] 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)

그래프란?

정점(node)과 그 정점을 연결하는 간선으로 이루어진 자료구조의 일종을 말한다.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문한다는 것을 말한다.

그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 방법으로 나뉜다.

💡깊이 우선 탐색(DFS)

: 루트 노드(Root Node) 혹은 다른 임의 노드(Node)에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

출처 https://developer-mac.tistory.com/64

미로찾기를 할 때 한 방향으로 가능한 만큼 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
• 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

장점

• 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

💡너비 우선 탐색(BFS)

: 루트 노드(Root Node) 혹은 다른 임의 노드(Node)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

출처 https://developer-mac.tistory.com/64

• 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

🔍깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 비교

🔍시간복잡도

DFS와 BFS모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
두 방식 모두 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N²)

참고
https://developer-mac.tistory.com/64
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