깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
그래프의 기본 구조
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차원 리스트를 이용하면 된다.
인접 리스트 방식 예제
# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
# 노드 0에서 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에서 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))
# 노드 2에서 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))
print(graph)
데이터의 개수가 N개인 경우 의 시간이 소요된다는 특징이 있다.
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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# dfs(graph, 1, visited)
1 2 7 6 8 3 4 5
의 시간이 소요
일반적인 경우 실제 수행 시간은 DFS보다 좋은 편
BFS 예제
from collections import deque
# BFS 메서드 정의
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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 | |
---|---|---|
동작 원리 | 스택 | 큐 |
구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
출처 : 이것이 코딩테스트다 with 파이썬