DFS와 BFS 알고리즘
작성 완료
- DFS 참고: 깊이 우선 탐색
- tree 구조
- stack 자료 구조 활용: 후입선출(한쪽면이 막힌 원통)
- 노드: [A], [B], [C], [D], [E], [F], [G], [H], [I], [J]
- 분기: [A, B, E], [A, B, F, I], [A, C, G], [A, D, H, I]
- 재귀함수를 활용한 DFS 코드가 최종 코드이다 (리스트 활용과 해시 테이블 활용 part에서 구현한 DFS는 비효율적임)
tree = {'A': ['B', 'C', 'D'], ## A는 B, C, D와 연결됨
'B': ['A', 'E', 'F'], ## B는 A, E, F와 연결됨
'C': ['A', 'G'], ## C는 A, G와 연결됨
'D': ['A', 'H'], ## D는 A, H와 연결됨
'E': ['B'], ## E는 B와 연결됨
'F': ['B', 'I'], ## F는 B, I와 연결됨
'G': ['C'], ## G는 C와 연결됨
'H': ['D', 'J'], ## H는 D, J와 연결됨
'I': ['F'], ## I는 F와 연결됨
'J': ['H']} ## J는 H와 연결됨
def DFS_list(graph, start_node):
visited = [] ## 방문한 노드
stack = [] ## 방문할 노드
stack.append(start_node) ## 방문할 노드에 시작 노드 추가
count = 0 ## 방문을 몇 번 했는지 기록
while stack: ## 방문할 노드가 있다면(리스트에 원소가 있으면 True)
node = stack.pop() ## node를 방문했다!, 마지막 노드 추가(스택 구조 사용)
count += 1 ## 방문 횟수 + 1
if node not in visited: ## 만약 아직 방문한 노드가 아니라면
visited.append(node) ## 이제 방문했으니까 방문한 노드에 추가
stack.extend(reversed(graph[node])) ## 방문한 노드에 연결된 노드를 탐색해보자
print(visited)
print(stack)
print('-------------------------------------------------------') ## 방문과정 확인
return visited, count ## 방문한 노드를 반환
DFS_list(tree, 'A') ## 마지막은 return 값
- return 결과를 보면 DFS 방식임을 알 수 있다
- 노드가 10개이므로 10번 방문해야 하지만 19번 방문함
- if node not in visited: ---> visited가 list인 경우 $O(N)$의 시간복잡도를 가짐
- visited도 해시 테이블(key: value 관계인 자료형: 파이썬의 dictionary)로 구현하면 $O(1)$로 효율$\uparrow$
- 해시 테이블에 관한 좋은 영상
def DFS_Hash_Table(graph, start_node):
visited = {} ## 방문한 노드
stack = [] ## 방문할 노드
stack.append(start_node) ## 방문할 노드에 시작 노드 추가
count = 0 ## 방문을 몇 번 했는지 기록
while stack: ## 방문할 노드가 있다면(리스트에 원소가 있으면 True)
node = stack.pop() ## node를 방문했다!, 마지막 노드 추가(스택 구조 사용)
count += 1 ## 방문 횟수 + 1
if node not in visited: ## 만약 아직 방문한 노드가 아니라면
visited[node] = True ## 이제 방문했으니까 방문한 노드에 추가
stack.extend(reversed(graph[node])) ## 방문한 노드에 연결된 노드를 탐색해보자
return list(visited.keys()), count ## 방문한 노드를 반환
DFS_Hash_Table(tree, 'A') ## 마지막은 return 값
- list를 활용한 코드와 return 결과는 동일하다
- 시간복잡도면에서 list를 활용한 것 보다 Hash Table을 사용한 것이 성능이 우월하다
- return 결과를 보면 DFS 방식임을 알 수 있다
- 노드가 10개이므로 10번 방문해야 하지만 19번 방문함
- 위에서 구현한 DFS는 방문을 한 뒤에 방문했다고 처리를 한다
- 방문을 하고 방문 처리를 하면 하나의 노드에 대해 중복 방문하므로 비효율적이다
- 아래와 같이 해당 노드를 방문할 때 방문 처리를 하면 중복 방문을 피할 수 있다
- 또한 재귀함수를 활용하여 코드를 더 간략하게 할 수 있다
count = 0 ## 방문 횟수
def DFS_recursive(graph, start_node, visited = {}):
global count
visited[start_node] = True ## 시작 정점 방문! (방문 처리)
count += 1 ## 방문 횟수 + 1
for node in graph[start_node]:
if node not in visited: ## 인접 노드를 아직 방문하지 않았다면
DFS_recursive(graph, node, visited) ## 방문하자!
## 간단히 설명 -> 처음 시작 노드는 'A' -> 'A'를 visited에 추가 'A'의 node는 ['B', 'C', 'D']
## -> 'B'는 아직 방문 안했음 -> 재귀함수 실행 -> 'B'를 start_node로 하여 visited에 추가 ->'B'의 node는 ['A', E', 'F']
## -> 'A'는 이미 방문했음 -> pass
## -> 'E'는 아직 방문 안했음 -> 재귀함수 실행 -> 'E'를 start_node로 하여 visited에 추가 -> 'E'의 node는 ['B']
## -> 'B'는 이미 방문했음 -> pass
## -> 'B'의 node로 'A', 'E' 방문 했고 이제 'F'만 남았음
## -> 'F'는 아직 방문 안했음 -> 재귀함수 실행 -> 'F'를 start_node로 하여 visited에 추가 -> 'F'의 node는 ['B', 'I']
## -> 'B'는 이미 방문했음 -> pass
## -> 'I'는 아직 방문 안했음 -> 재귀함수 실행 -> 'I'를 start_node로 하여 visited에 추가 -> 'I'의 node는 [F]
## -> 'F'는 이미 방문했음 -> pass
## -> 'A'의 node인 ['B', 'C', 'D']중 'B'를 방문 끝냈으므로 'B'를 탐색했던 것처럼 나머지 'C'와 'D'도 탐색하면 끝임
return list(visited.keys()), count
DFS_recursive(tree, 'A')
- 재귀함수를 사용하여 방문한 노드를 visited에 추가한다
- return 결과를 보면 DFS 방식임을 알 수 있다
- 노드가 10개이므로 10번 방문했다 (리스트 활용과 해시 테이블 활용 part에선 쓸데없이 19번 방문했다)
- 모든 정점을 한번만 방문
- 시작 노드에서 인접한 다음 분기로 넘어가면서 탐색
- 넘어갈 분기가 없으면 하위 노드를 탐색
- 방문할 노드와 방문한 노드를 기준으로 탐색
- 특정 노드가 방문할 노드 ---> 탐색, 방문한 노드 ---> 지나감
- 그래프나 트리는 dictionary로 생성
- queue 구조로 구현 가능
- 출발노드에서 목표노드까지의 최단 길이 경로를 보장
- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요
- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝남
- 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못함
- BFS 참고: 너비 우선 탐색
- tree 구조
- queue 자료 구조 활용: 선입선출(양쪽 면이 뚫린 원통)
- 노드: [A], [B], [C], [D], [E], [F], [G], [H], [I], [J]
- 분기: [A, B, E], [A, B, F, I], [A, C, G], [A, D, H, I]
- 성능이 좋음 ---> $O(1)$
- 사용: from collections import deque
- 만약 queue = list()라면 queue.pop(0)을 해야함 ---> $O(N)$
- deque를 사용하여 queue.pop(0)대신 queue.popleft() 사용 ---> $O(1)$
- DFS와 마찬가지로 visited는 해시 테이블로 구현
- 방문 하기 전에 방문 처리를 해야 한다
- 만약, 방문을 하고 나서 방문 처리를 하면 중복 방문을 하게 되므로 비효율적임
def BFS_queue(graph, start_node):
from collections import deque ## deque패키지 import
queue = deque() ## 방문할 노드
queue.append(start_node) ## 방문할 노드에 시작 노드 추가
visited = {} ## 방문한 노드
visited[start_node] = True ## 시작 정점을 방문!
count = 0 ## 방문 횟수
while queue: ## 방문할 노드가 있다면(리스트에 원소가 있으면 True)
u = queue.popleft() ## 노드 u를 방문하자!
count += 1 ## 방문 횟수 + 1
print(list(visited.keys())) ## 방문한 노드
for v in graph[u]:
if v not in visited: ## 만약 아직 방문한 노드가 아니라면
visited[v] = True ## 이제 방문했으니까 방문한 노드에 추가 (방문 처리)
queue.append(v) ## 방문한 노드에 연결된 노드를 탐색해보자
print(queue) ## 방문할 노드 (popleft 하기 전에 방문 체크를 미리해서 실질적으로 방문할 노드와 차이가 있음)
print('-------------------------------------------------------') ## 방문과정 확인
return list(visited.keys()), count ## 방문한 노드를 반환
BFS_queue(tree, 'A')
- return 결과를 보면 BFS 방식임을 알 수 있다
- popleft 하기 전에 방문 체크를 미리해서 출력을 보면 방문한 노드와 방문할 노드에 중복으로 들어간 원소가 있음
- 문제가 있는 것 같지만 BFS는 정확히 원소 개수인 10번만큼 방문했다! (한 번에 하니씩 popleft 하기 때문에 시간 상에 차이가 있어서 그런 것)