DFS와 BFS는 모두 그래프를 탐색하는 방법이다.
그래프는 나중에 더 자세히 작성할건데, 일단 이번에 필요한만큼만 먼저 정리해보도록 하겠다.
: 정점(node)과 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종
🔎 그래프를 탐색한다는 것은 하나의 정점에서부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것이다.
다음 그래프를 파이썬으로 구현하려면 어떻게 해야할까?
graph = [[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]]
graph = [
[1, 2, 3],
[0, 3],
[0, 3],
[0, 1, 2]
]
# or
graph_dict = {
0:[1, 2, 3],
1:[0, 3],
2:[0, 3],
3:[0, 1, 2]
}
깊이 우선 탐색 (Depth-First-Search)
DFS의 동작원리는 스택 자료구조에 기초한다.
- 시작노드를 스택에 삽입하고 방문 처리한다.
- 스택의 최상단 노드에 인접한 노드들 중 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 인접한 모든 노드들을 방문했다면, 스택에서 최상단 노드를 꺼낸다.
- 2번 과정을 수행할 수 없을때까지 반복한다.
전체 노드의 탐색 순서 : 1
→ 2
→ 7
→ 6
→ 8
→ 3
→ 4
→ 5
DFS는 스택이나 재귀함수로 구현한다.
동작원리는 스택 자료구조에 기초하지만, 구현할때 실제로 스택을 쓰지는 않아도 된다. 오히려 재귀함수로 구현했을때 코드가 간결해진다.
아래 예시에서 그래프는 모두 인접리스트로 나타낸다.
graph = { # 번호가 작은 인접노드부터 사용하기 위해 내림차순 정렬
1:[8,3,2],
2:[7,1],
3:[5,4,1],
4:[5,3],
5:[4,3],
6:[7],
7:[8,6,2],
8:[7,1]
}
def dfs_stack(graph, v):
stack = [v] # 스택에 루트노드 삽입
visited = [] # 방문처리한 노드가 담길 곳
while stack: # 스택이 빌 때까지 반복
top = stack.pop() # 스택의 최상단 노드 빼기
if top not in visited: # 아직 방문하지 않았었다면
print(top, end=' ')
visited.append(top) # 방문 처리
for i in graph[top]: # 최상단노드와 인접한 노드 중
if i not in visited:
stack.append(i) # 아직 방문하지 않은 노드들 스택에 삽입
dfs_stack(graph, 1) # 매개변수 : (탐색할 그래프, 루트노드)
# 1 2 7 6 8 3 4 5
위의 설명에서 사용한 스택의 사용법과는 살짝 다르다. 코드의 효율성을 위해 인접한 노드 중 가장 번호가 작은 노드 1개만 스택에 넣는 것이 아니라, 인접한 노드를 순서에 맞춰서 (번호가 작은것부터 쓰기 위해서는 내림차순으로) 모두 넣고 top에서 뽑아쓰는 형식이다.
graph = { # 작은 번호부터 사용하기 위해 오름차순 정렬
1:[2,3,8],
2:[1,7],
3:[1,4,5],
4:[3,5],
5:[3,4],
6:[7],
7:[2,6,8],
8:[1,7]
}
visited = [False] * 9
def dfs_recursion(graph, v, visited):
visited[v] = True # 현재노드 방문처리
print(v, end=' ')
for i in graph[v]: # 현재노드와 인접한 노드 중
if not visited[i]: # 아직 방문하지 않은 노드는
dfs_recursion(graph, i, visited) # 재귀호출
dfs_recursion(graph, 1, visited) # 매개변수 : (탐색할 그래프, 시작노드, 방문여부)
# 1 2 7 6 8 3 4 5
코드가 훨씬 간결해졌다.
재귀 호출 순서는 아래와 같다.
엄청 복잡한데 별다른 추가코드도 없이 재귀함수 호출 순서 자체가 DFS 탐색 순서와 똑같은게 신기하다.
너비 우선 탐색 (Breadth-First-Search)
BFS의 동작원리는 큐 자료구조에 기초한다.
- 시작노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고 방문 처리한다.
- 2번 과정을 수행할 수 없을때까지 반복한다.
전체노드의 탐색 순서 : 1
→ 2
→ 3
→ 8
→ 7
→ 4
→ 5
→ 6
BFS는 큐로 구현한다.
DFS와 달리 BFS는 동작원리와 구현방법이 동일하다.
아래 예시에서 그래프는 모두 인접리스트로 나타낸다.
from collections import deque
graph = {
1:[2,3,8],
2:[1,7],
3:[1,4,5],
4:[3,5],
5:[3,4],
6:[7],
7:[2,6,8],
8:[1,7]
}
visited = [False] * 9
def bfs(graph, v, visited):
queue = deque([v]) # 큐에 루트노드 삽입
visited[v] = True # 루트노드 방문처리
while queue: # 큐가 빌때까지 반복
v = queue.popleft() # 넣은지 제일 오래된 노드 빼서
print(v, end=' ')
for i in graph[v]: # 이 노드와 인접한 노드 중
if not visited[i]: # 아직 방문하지 않은 노드들은
queue.append(i) # 큐에 삽입하고
visited[i] = True # 방문처리
bfs(graph, 1, visited) # 매개변수 : (탐색할 그래프, 루트노드, 방문여부)
# 1 2 3 8 7 4 5 6
위의 설명과 동일한 코드이다.
DFS와 BFS 모두 조건 내의 모든 노드를 검색하기 때문에 시간복잡도는 동일하다.
노드가 N
개, 간선이 E
개인 그래프를 탐색한다면 구현방법에 따라 시간복잡도는 아래와 같이 달라진다.
O(N+E)
O(N^2)
보통 E
가 N^2
보다 작기 때문에 인접리스트 방식이 효율적이다.
내용이 너무 길어져서 코드리뷰는 (2)편으로
저도 개발자인데 같이 교류 많이 해봐요 ㅎㅎ! 서로 화이팅합시다!