5. DFS / BFS - 이론
그래프 이론 을 참고하자!
✨ DFS
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택사용
1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.
2. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복한다.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택사용
1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.
2. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복한다.
(방문처리는 스택에 한 법 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.)
# DEF 메서드 정의
def DFS(graph, v, visited) :
# 현재 노드를 방문 처리
visisted[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] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
✨ BFS
가까운 노드부터 탐색하는 알고리즘
큐 사용
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
가까운 노드부터 탐색하는 알고리즘
큐 사용
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
코테에서는 보통 DFS보다 BFS가 더 빠르게 동작한다.
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited) :
# 큐 구현을 위해 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)
Author And Source
이 문제에 관하여(5. DFS / BFS - 이론), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yesterdaykite/5.-DFS-BFS-이론저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)