[알고리즘] DFS / BFS
DFS(깊이 우선 탐색)
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다
- 더 이상의 수행이 없을 때까지 반복
- 방문하지 않은 노드가 없으면 pop
- visited를 통해 방문 여부 체크
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True;
print(v, end = ' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
# 방문하지 않은 노드만
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited) # 재귀함수 호출
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원)
visited = [False] * len(graph) # len(graph) == 9
# dfs 메서드 호출
dfs(graph, 1, visited)
# 출력결과 : 1 2 7 6 8 3 4 5
BFS(너비 우선 탐색)
가까운 노드부터 탐색하는 알고리즘
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상의 수행이 없을 때까지 반복
- 꺼내서(dequeue) 방문하지 않은 노드 체크
- 일반적인 경우, 실제 수행 시간은 DFS보다 좋은 편(노드의 수가 적고, 깊이가 얕을 때 빠름)
- 너비를 우선 탐색하기 때문에, 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
최단 경로가 존재하면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 찾을 수 있음- queue 라이브러리, visited 이용
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# start를 enqueue한 채로 queue 생성
queue = deque([start])
# 시작 노드 방문 처리
visited[start] = True
while queue: # 큐가 empty면 종료
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]
]
visited = [False] * len(graph)
bfs(graph, 1, visited)
# 출력결과 : 1 2 3 8 7 4 5 6
Author And Source
이 문제에 관하여([알고리즘] DFS / BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ayoung0073/algorithm-DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)