이번 글에서는 그래프 탐색 알고리즘인 DFS(Depth-First-Search)과 BFS(Breadth-First-Search)에 대해서 파이썬 예제 코드로 알아볼 것이다.
DFS(깊이 우선 탐색)
DFS는 깊이 우선 탐색이라고도 하고 깊이를 우선으로 탐색한다. 위 그림처럼 최대한 깊이 내려간 뒤 더이상 내려갈 곳이 없다면 옆으로 이동하는 방식이다.
특징
- 모든 노드를 방문하고자 할 때 사용됨
- BFS에 비해 비교적 간단함
- 검색 속도는 BFS에 비해 느림
- 스택이나 재귀함수를 이용하여 구현
BFS(너비 우선 탐색)
BFS란 너비 우선 탐색이라고도 하고 깊이보단 너비를 우선적으로 탐색하는 알고리즘이다. 위 그림처럼 최대한 옆으로 이동한 후 더이상 옆으로 갈 수없다면 아래로 내려가서 검색하는 방식이다.
특징
- 최단 경로를 찾고자 할 때 사용 - 그림의 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있음
- 큐를 사용하여 구현
DFS 파이썬 예제
위 그림과 같은 그래프가 있다고 가정했을 때의 파이썬 예제이다.
DFS는 기본적으로 방문해야할 노드와 방문한 노드 목록을 기준으로 데이터를 탐색한다. 방문해야할 노드 목록이 계속 추가가 되고 그 목록의 마지막 값부터 읽기 때문에 깊이 탐색이 가능하다.
g = dict()
g['A'] = ['B', 'C', 'D']
g['B'] = ['A', 'E']
g['C'] = ['A', 'F','G']
g['D'] = ['A', 'H']
g['E'] = ['B', 'I']
g['F'] = ['C', 'J']
g['G'] = ['C']
g['H'] = ['D']
g['I'] = ['E']
g['J'] = ['F']
def dfs(graph, start_node):
#방문할 노드와 방문한 노드 두 개를 리스트로 지정
need_visited, visited= list(), list()
#시작 노드 지정하기
need_visited.append(start_node)
#print(need_visited)
# 더 이상 방문할 노드가 없을 때까지
while need_visited:
#시작 노드를 pop방식으로 마지막 값을 꺼내서 node에 저장(스택 구조의 활용)
print(f'need_visited = {need_visited}')
node = need_visited.pop()
print(f'node = {node}')
#만약 node가 방문한 목록에 없다면
if node not in visited:
#방문한 목록에 node 추가
visited.append(node)
#그 node에 연결된 다른 노드들도 추가, g dict의 값을 왼쪽부터 오른쪽으로 입력했고 pop이 제일 마지막부터 꺼내기 때문에 오른쪽부터 탐색하게됨.... 따라서 reversed 사용해서 왼쪽부터 탐색하게 함. dict 구조라 g[node]의 밸류인 연결된 노드들이 들어감
need_visited.extend(reversed(graph[node]))
return visited
dfs_test = dfs(g, 'A')
print(dfs_test)
출력 결과 그대로 동작한다.
BFS 파이썬 예제
마찬가지로 위와 같은 그래프가 있다고 가정했을 때의 파이썬 예제이다.
방문할 노드 목록과 방문한 노드 목록을 기준으로 데이터를 탐색한다.
전제 조건은 그래프를 dict 형태로 데이터 입력할 때 A~J 순서, 왼쪽부터 입력해야 올바르게 탐색이 가능함.
과정을 요약하자면,
1. 시작 노드를 방문했던 노드에 삽입
2. 방문할 노드에 시작 노드의 Child Node를 삽입
3. Child 노드를 중심으로 다시 1~2단계 수행
BFS와 DFS의 가장 큰 차이점은 While문 다음에 어떤 자료를 우선적으로 추출하느냐이다.
DFS 같은 경우 방문해야할 노드 목록의 가장 끝에 있는 데이터를 기준으로 추출해서 탐색하지만, BFS는 목록의 가장 처음에 있는 인자를 받아서 탐색한다. 그렇게 되면 같은 Depth에 있는 노드부터 탐색하게 된다.
g = dict()
g['A'] = ['B', 'C', 'D']
g['B'] = ['A', 'E']
g['C'] = ['A', 'F', 'G']
g['D'] = ['A', 'H']
g['E'] = ['B', 'I']
g['F'] = ['C', 'J']
g['G'] = ['C']
g['H'] = ['D']
g['I'] = ['E']
g['J'] = ['F']
def bfs(graph, start_node):
#방문할 노드와 방문한 노드 두 개를 리스트로 지정
need_visited, visited= list(), list()
#시작 노드 지정하기, dict 구조라 키 입력하면 밸류가 들어감
need_visited.append(start_node)
# 더 이상 방문할 노드가 없을 때까지
while need_visited:
#시작 노드를 pop방식으로 꺼내서 node에 저장. DFS와는 다르게 마지막 값이 아닌 첫번째 값을 꺼냄(큐 구조의 활용)
print(need_visited)
node = need_visited.pop(0)
#만약 node가 방문한 목록에 없다면
if node not in visited:
#방문한 목록에 node 추가
visited.append(node)
#해당 node에 연결된 다른 노드 추가, g dict에 왼쪽부터 순서대로 값을 입력했기 때문에 need_visited에는 A~J
need_visited.extend(graph[node])
return visited
bfs_test = bfs(g, 'A')
print(bfs_test)
출력 결과, 그대로 작동한다.
참고
https://codingopera.tistory.com/67
https://data-marketing-bk.tistory.com/44
'알고리즘' 카테고리의 다른 글
| 프로그래머스 - 문자열 나누기(파이썬) (0) | 2024.02.02 |
|---|