그래프 탐색 알고리즘: DFS / BFS
- 탐색(Search)란 많은 야의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
- 대표적으로 DFS / BFS가 있다.
BFS/ DFS를 알기전 스택과 큐 자료구조에 대헤 이해하면 도움이 된다.
스택(Stack)과 큐(Queue) 자료구조
- 후입선출 (Last-in-First-out)로 이루어지는 자료구조이다
- 입구와 출구가 동일한 박스 쌓기라 생각하면 편하다.
-
스택 자료구조
파이썬에서 쉽게 스택 자료구조를 이용하기 위해서는 list를 사용하여 append() 통하여 데이터를 삽입하고, pop()을 통하여 데이터를 삭제할 수 있다. 다른 라이브러리를 불러오지 않아도 된다. -
큐 자료구조
머저 들어온 데이터가 먼저 나가는 (First-in-First-out)자료구조를 가진다.
터널에 데이터가 들어와 나간다 생각하면 이해하기 쉽다.
파이썬 에서는 deque 라이브러리를 이용하여 큐 자료구조를 이용하고 삽입시에는 append(), 삭제할 때에는 popleft()를 사용하면 된다. quue는 스택과 큐의 장점을 합친 라이브러리이다.
재귀함수 (Recursive Function)
- 재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.
# '재귀 함수를 호출합니다.'를 무한 반복하는 함수
def recursive_function():
printt('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()- 재귀 함수를 사용할 때에는 종료 조건을 명시하지 않으면 함수가 무한히 호출 될 수 있기 때문에 종료조건을 반드시 명시해야 한다.
# '재귀 함수를 호출합니다.'를 무한 반복하는 함수
def recursive_function(i):
# 100 번째 호출을 했을 때 종료 되도록 조건 추가
if i==100:
return
printt(i, '번째 재귀 함수에서', i+1, '번째 재귀함수를 호출 합니다.')
recursive_function(i+1)
printt(i, '번째 재귀함수를 종료합니다.')
recursive_function()- 재귀함수 예제 (팩토리얼 구현하기
def factorial_recursive(i):
if i <=1:
return 1
# n! = n * (n-1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n-1) 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
또한 모든 재귀 함수는 반복문을 활용하여 동일한 기능을 구현할 수 있다.
컴퓨터가 함수를 연속적으로 호출하는 경우 컴퓨터 메모리 내부의 스택 프레임에 쌓여, 스택을 사용해야 하는 경우 구현상 스택 라이브러리 대신에 재귀 함수를 이용 하는 경우가 많다.
DFS (Depth-First Search)
DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드르 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
다음과 같은 그래프가 있다고 할때 DFS를 파이썬으로 구현 보면서 이해하면 쉽다. (방문 기준: 번호가 낮은 인접노드 부터)
# 코드 출처
# https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
# DFS 메서드 정의
#그래프 array, 시작 위치, 방문 정보가 들어있는 리스트
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노트와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # grqph[i]에 있는 원소가 방문되어 잇지 않다면 재귀함수 호출
dfs[graph, v, visited)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[],
[2,3,8], # 1번 노트와 연결된 정보
[1,7], # 2번 노드와 연결된 정도
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현
visited = [False] * lend(graph)
# 정의된 DFS 함수 호출
dfs(graph, 1, visted)
# 출력 (1 2 7 8 3 4 5)
BFS (Breadth-First Search)
BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
BFS는 큐 자료구조를 이요하며, 구체적인 동작 과정은 다음과 같다.
-
탐색 시작 노드를 큐에 삽입하고 밤문처리를 한다.
-
큐에서 노드르 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
-
더이상 뒤 위 과정을 수행할 수 없을 때까지 반복한다.
다음과 같은 그래프가 있다고 할때 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번 노트와 연결된 정보
[1,7], # 2번 노드와 연결된 정도
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현
visited = [False] * lend(graph)
# 정의된 DFS 함수 호출
dfs(graph, 1, visted)
# 출력 (1 2 3 8 7 4 5 6)
