DFS 와 BFS 는 그래프를 탐색하는 방법으로, 어떤 기준으로 그래프를 읽어가느냐에 따른 차이가 있다.
그래프란?
- 정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 일종의 자료구조
- 정점 : 특별한 하나의 객체
- 간성 : 두 개의 노드를 연결하는 선, 두 노드간의 관례를 나타낸다. 방향이나 비중을 가질 수 있다.
- 그래프를 탐색한다 = 하나의 정점을 시작으로 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다!
DFS 깊이 우선 탐색
DFS : Depth-First Search
루트 노드에서 탐색을 시작할 때, 연결되어 갈 수 있는 데까지 최대한 깊게 끝까지 탐색하는 방식이다.
찾아보니 미로찾기를 할 때, 한 방향으로 가다가 막히면 다시 가장 가까운 갈림길로 돌아와서 그 곳부터 다른 방향으로 탐색을 진행하는 것과 같은 방식이라고 설명하고 있다.
- 스택(Stack) 혹은 재귀함수(Recursion)으로 구현
- 스택의 접시 쌓기와 같다고 생각하면 되는데, 위에 꺼를 빼지 않으면 아래 것을 먼저 쓸 수 없고 순서대로 빼야 한다는 개념이다. (중간에 빼기 없기)
- 재귀함수로 가능한 이유도, 함수가 콜스택에 쌓이는 방식이기 때문이다.
- 검색 속도 자체는 BFS(너비 우선 탐색)에 비해 느리다.
스택과 재귀함수로 구현될 때, 스택의 개념을 쓴다는 것은 같지만 완전히 똑같지는 않다.
- 함수에서는 순서를 변경 할 수 없지만, 스택을 사용할 때 순서를 지정해서 하고 싶다면 정렬을 반대한다던지의 방법으로 변경해서 사용할 수 있다.
예시)
1-2-3-4로 스택이 쌓이고 만약 2와 3, 4에도 연결된 노드들이 있더라도 제일 마지막인 4와 연결된 것부터 탐색하고 3과 연결된 노드를 탐색하고 2와 연결된 노드를 탐색하게 된다.
만약 탐색 자체를 2부터 하고 싶다면, 정렬을 반대로 해서 처음부터 스택이 1-4-3-2 로 쌓이도록 하여 탐색할 수도 있다.
BFS 너비 우선 탐색
BFS : Breadth-First Search
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하고, 멀리 떨어져 있는 노드는 나중에 탐색하는 방식이다.
- que 큐로 구현
- 넣은 자료들 중에 제일 앞에 있는 것(제일 가까운 것)을 먼저 선택해서 탐색하는 과정이다.
- 식당 줄서기와 같은 느낌.. 맨 앞에 부터 진행되는 것
- 최단 거리를 찾기에 좋다. 가까운 것부터 탐색하기 때문에
DFS, BFS 시간 복잡도
두 가지 방법 모두 모든 노드를 탐색한다는 점에서 시간복잡도는 동일하다.
(다음 노드를 방문하였는지 확인하는 시간 + 각 노드를 방문하는 시간) 으로 계산된다.
N 노드, E 간선 일 때,
- 인접 리스트 : O(N+E)
- 인접 행렬 : O(N^2)
일반 적으로 E(간선)의 크기가 N^2 에 비해 상대적으로 적기 떄문에, 인접 리스트 방식이 효율적이다.
활용 유형
- 그래프의 모든 정점을 방문 해야 할 때
단순히 전체 탐색일 경우에는 DFS, BFS 어떤 것도 상관 없으므로 편한 걸 쓴다. - 경로의 특징을 저장해둬야 할 때
각 노드에 숫자가 적혀있고, a - b 이동하는 경로를 구하는데, 경로에 같은 숫자가 있으면 안된다 처럼 각 경로의 특징을 저장해둬야 한다면, DFS 를 사용한다.
(BFS 는 경롱의 특성을 저장할 수 없다.) - 최단 거리 를 구할 떄
BFS 를 사용한다. 현재 노드에서 가까운 노드부터 찾기 때문에 경로 탐색 시, 먼저 찾아지는 결과가 곧 최단 거리가 된다. - 검색 대상 그래프가 너무 크다? - DFS 고려
- 검색 대상의 규모가 크지 않고, 검색 시작 지점부터 대상이 멀지 않다면? - BFS 고려
파이썬 코드
기본적으로 입력으로 주어지는 그래프를 그리고, 그래프 만큼의 방문 기록을 확인 할 수 있는 visited 리스트를 false로 만들어서 방문했던 노드는 재방문 하지 않기 위해 방문 여부를 남힌다. (안해주면 무한 재방문이 될 수도 있음)
1-1. DFS - stack
def dfs(idx):
stack = []
# 시작점을 스택에 쌓아준다. _ 방문해야 할 노드 저장
stack.append(idx)
# 스택이 존재하는 동안 반복함
while stack:
#지금 방문한 노드 = 시작점 이후에는 스택에서 제일 마지막에 저장 한 노드
current = stack.pop()
# 확인용 출력
print(f"{current} 방문!")
# 방문 했다면 True 로 변경해준다.
visited[current] = True
#지금 방문 노드의 인접한 노드를 탐색하는데,
for adj in graph[current]:
# 방문하지 않았는지 확인 후,
if not visited[adj]:
# 연결되어 있는 노드를 스택에 쌓아준다.
stack.append(adj)
# 재방문을 막기 위해 방문 처리
visited[adj] = True
# 그래프 초기 설정
n = 5
graph = [[] for _ in range(n + 1)]
graph[1].append(2)
graph[1].append(4)
graph[2].append(4)
graph[4].append(1)
graph[4].append(5)
graph[5].append(3)
# graph = [[], [2, 4], [4], [], [1, 5], [3]]
# 방문 여부 확인용 리스트 (인덱스를 1부터 사용하기 위해 n+1 까지)
visited = [False] * (n + 1)
# dfs 그래프 탐색
dfs(1)요렇게 쓰면 출력 결과는
# 결과값
1 방문! # 1 방문, stack = [2, 4]
4 방문! # 1-4 으로 방문, stack = [2, 5]
5 방문! # 4-5 으로 방문, stack = [2, 3]
3 방문! # 5-3 으로 방문, stack = [2]
2 방문! # 마지막 남은 노드 방문1-2. DFS - 재귀함수
def dfs(idx):
if visited[idx]: # 방문한 노드는 다시 방문할 필요 없으므로 체크해줌
return
visited[idx] = True # 노드 방문 처리
# 확인용 출력
print(f"{idx} 방문!")
for i in graph[idx]: # 주변 노드들에 대한 탐색을 위해 재귀함수로 호출
dfs(i)
# 그래프 초기 설정 _이 부분은 동일
n = 5
graph = [[] for _ in range(n + 1)]
graph[1].append(2)
graph[1].append(4)
graph[2].append(4)
graph[4].append(1)
graph[4].append(5)
graph[5].append(3)
visited = [False] * (n + 1)
dfs(1)2. BFS - que
def bfs(idx):
from collections import deque
queue = deque()
queue.append(idx)
# 노드 방문 처리
visited[idx] = True
# 큐가 비어 있을 때까지 탐색
while queue:
# 큐에 들어온 순서대로 제일 앞의 노드를 뽑아서
idx = queue.popleft()
print(f"{idx} 방문!")
for i in graph[idx]:
# 방문하지 않았을 때
if not visited[i]:
# 큐에 추가
queue.append(i)
visited[i] = True
# 그래프 초기 설정_ 이 부분은 모두 같음
n = 5
graph = [[] for _ in range(n + 1)]
graph[1].append(2)
graph[1].append(4)
graph[2].append(4)
graph[4].append(1)
graph[4].append(5)
graph[5].append(3)
# graph = [[], [2, 4], [4], [], [1, 5], [3]]
visited = [False] * (n + 1)
# 탐색 시작
bfs(1)그럼 결과는 아래처럼 나오게 된다!
# 결과값
1 방문! # q = [2, 4]
2 방문! # q = [4]
4 방문! # q = [5]
5 방문! # q = [3]
3 방문!참고자료
DFS, BFS의 설명, 차이점
항해99 강의자료
