DFS & BFS란?
•
그래프의 모든 정점을 순회하는 탐색 방법 : 대표적으로 2가지 존재
◦
깊이우선탐색(DFS)
◦
너비우선탐색(BFS)
•
참고) DFS, BFS는 그래프 탐색 방법이지만, 트리에도 사용 가능
◦
트리는 특수한 경우의 그래프라고 할 수 있기 때문
깊이우선탐색(DFS)
Depth-First Search
•
더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법
•
깊이우선탐색에 사용되는 자료구조 : 배열(리스트) & 스택
◦
배열 : 특정 정점의 방문 여부를 확인하기 위해 사용
◦
스택 : 방문 중 뒤로가기가 필요할 때 사용
너비우선탐색(BFS)
Breadth First Search
•
최대한 넓게 탐색하기를 반복하는 방법
•
너비우선탐색에 사용되는 자료구조 : 배열(리스트) & 큐
◦
배열 : 특정 정점의 방문 여부를 확인하기 위해 사용
◦
큐 : 연결된 정점들을 저장하기 위해 사용
▪
특정 정점과 인접한 모든 정점을 줄 세우듯 저장하고, 앞으로 어떤 정점에서 너비 우선 탐색을 할지 알기 위해 큐를 사용
코드로 확인해볼까요?
깊이우선탐색(DFS)
재귀
# 1~8번 노드의 연결관계를 연결리스트로 표현
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
def dfs(graph, node, visited):
visited[node] = True
print(node, end=' ')
for next_node in graph[node]:
if visited[next_node] == False:
dfs(graph, next_node, visited)
dfs(g, 1, visited) # 1 2 7 6 8 3 4 5
Python
복사
스택
# 1~8번 노드의 연결관계를 연결리스트로 표현
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
stack = []
def dfs(graph, node, visited, stack):
visited[node] = True
stack.append(node)
while stack:
current_node = stack.pop()
print(current_node, end=' ')
for next_node in reversed(graph[current_node]):
if visited[next_node] == False:
visited[next_node] = True
stack.append(next_node)
dfs(g, 1, visited, stack) # 1 2 7 6 8 3 4 5
Python
복사
너비우선탐색(BFS)
from collections import deque
# 1~8번 노드의 연결관계를 연결리스트로 표현
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
def bfs(graph, node, visited):
queue = deque()
visited[node] = True
queue.append(node)
while queue:
current_node = queue.popleft()
print(current_node, end=' ')
for next_node in graph[current_node]:
if visited[next_node] == False:
queue.append(next_node)
visited[next_node] = True
bfs(g, 1, visited] # 1 2 3 8 7 4 5 6
Python
복사