DFS(깊이우선탐색)
- Depth first search의 약자로 그래프 자료에서 데이터를 탐색하는 알고리즘이다.
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 위의 그래프와 같이 더 이상 찾아내려갈 수 없을 때 까지 깊게 탐색하는 알고리즘이다.
DFS 구현
- DFS는 항상 앞으로 찾아 가야 할 노드와 이미 방문한 노드를 기준으로 탐색한다.
- 즉 특정 노드가 앞으로 찾아 가야 할 노드라면 계속 탐색을 해 나가는 것이고, 이미 방문한 노드라면 무시하거나 따로 저장하면 된다.
- 아래의 코드는 위의 그래프 사진을 딕셔너리로 표현한 것이다.
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
- deque를 활용 한 DFS구현
def dfs(graph, start_node):
# 방문한 노드를 담을 리스트
visited = []
# 방문해야 할 노드를 담을 deque
need_visited = deque()
#시작 노드 설정해주기
need_visited.append(start_node)
# 방문이 필요한 리스트가 아직 존재한다면
while need_visited:
# 시작 노드를 지정하고
node = need_visited.pop()
#만약 방문한 리스트에 없다면
if node not in visited:
# 방문 리스트에 노드를 추가
visited.append(node)
# 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited
print(dfs(graph, 'A')) => ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
재귀함수를 이용한 DFS구현
def dfs_recursive(graph, start, visited):
# 방문 한 노드를 담을 리스트
# 시작노드 추가
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
visited = []
재귀함수를 이용한 DFS구현2
def dfs(graph, v, visited):
#v는 시작위치
visited[v] = True
print(v , end = ' ')
#현재 노드와 연결된 노드를 재귀적으로 호출
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2,3,7],
[1,4,6],
[1,5, 7],
[2,6],
[3,7],
[2,4],
[1,3]
]
#각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False] * 9
dfs(graph, 1, visited) => 1 2 4 6 3 5 7
BFS(Breadth First Search/ 너비 우선 탐색)
- BFS란
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
- 시작 정점에 가까이 있는 정점부터 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문 하는 순회 방법이다.
- 즉, DFS와는 다르게 넓게 탐색하는 방법이다.
- BFS의 특징
- DFS와는 다르게 재귀적을 동작하지 않는다.
- 어떤 노드를 방문했었는지에 대한 여부를 반드시 검사해야 한다.
이를 검사하지 않을 시 무한루프에 빠질 수 있다.
- 선입선출(FIFO)를 원칙으로 탐색하며 deque를 사용하여 구현할 수 있다.
- BFS의 탐색 과정
- 탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
- 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.
- 2번의 과정을 더 이상 수행할 수 없을때까지 반복한다.
- BFS 소스코드 예제(Python)
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)
백준 BFS 문제