DFS/BFS 탐색 알고리즘
그래프
그래프는 노드(정점)와 간선으로 표현됨.
그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
그래프의 표현 방식
1. 인접 행렬
- 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 2차월 배열에 각 노드가 연결된 형태를 기록하는 방식
- 파이썬에서는 2차원 리스트로 구현 가능
- 연결 되어 있지 않은 노드끼리는 무한의 비용이라고 작성
인접 행렬 방식 예제
INF = 999999999 #무한의 비용 선언
#2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph) #[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]
2. 인접 리스트
- 리스트로 그래프의 연결 관계를 표현하는 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- 인접 리스트는 '연결 리스트'라는 자료구조를 이용해 구현함
- C++, 자바에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공함
- 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공함
- 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 됨
인접 리스트 방식 예제
graph = [[] for _ in range(3)] #행이 3개인 2차원 리스트로 인접 리스트 표현
graph[0].append((1, 7)) #노드 0에 연결된 노드 정보 저장
graph[0].append((2, 5))
graph[1].append((0, 7)) #노드 1에 연결된 노드 정보 저장
graph[2].append((0, 5)) #노드 2에 연결된 노드 정보 저장
차이점
- 메모리 측면
· 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨
· 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용
노드 1과 노드 7이 연결되어 있는지 확인할 때 인접 행렬의 경우 grpah[1][7] 과 같이 바로 그 좌표를 통해 확인할 수 있음.
반면에 인접 리스트의 경우 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 함.
→ 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 메모리 공간의 낭비가 적음.
DFS
- DFS는 Depth First Search, 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 특정한 경로로 탐색하다가 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
- 동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
- 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리함
- DFS는 스택 자료구조에 기초함 → 구현이 간단함
- 데이터의 개수가 N개인 경우 시간복잡도는 O(N)
- DFS는 스택을 이용하므로 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 표현 가능
DFS 예제
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[], #대부분 노드 1부터 시작하므로 인덱스 0 비워둠
[2, 3, 8], #노드 1과 인접한 노드
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7],
]
visited = [False] * 9
dfs(graph, 1, visited) # > [1, 2, 7, 6, 8, 3, 4, 5]BFS
- BFS는 Breadth First Search, 너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘
- 선입선출 방식인 큐 자료구조 이용
- 동작 과정
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
BFS 예제
from collections import deque
def bfs(graph, start, visited):
# Queue 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=" ")
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 인접 리스트 방식
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6
| DFS | BFS | |
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |