:: DFS
Depth-First Search
- 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
(실제로 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)
# 각 노드가 연결된 정보를 표현 ( 2차원 리스트 )
graph = [
[], # 인덱스 0에 해당되는 노드는 비워둠
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 ( 1차원 리스트 )
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
# 실행결과 : 1 2 7 6 8 3 4 5
:: BFS
Breadth-First Search
- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복한다.
(BFS 알고리즘은 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로 효과적으로 사용될 수 있다.)
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited) :
# 큐 구현을 위해 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 = [
[], # 인덱스 0에 해당되는 노드는 비워둠
[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
댓글