항해99 2주차 - 그래프(DFS/BFS) 이론 정리
Today I learned
2022/01/20
회고록
1/20
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
1. 이론
DFS와 BFS
DFS와 BFS는 그래프의 탐색 방법
목적: 한 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문
DFS
한 우물을 깊이 파면서 탐색
재귀함수 혹은 스택으로 구현 가능
d_check = [False for _ in range(n + 1)]
def dfs(x):
d_check[x] = True
print(x, end = ' ')
for y in edge[x]:
if d_check[y] == False:
dfs(y)
BFS
여러 우물을 동시에 같은 깊이로 탐색
최단 경로 찾기에 사용
from collections import deque
def bfs():
queue = deque([start])
b_check = [False for _ in range(n + 1)]
b_check[start] = True
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in edge[v]:
if not b_check[i]:
b_check[i] = True
queue.append(i)
Author And Source
이 문제에 관하여(항해99 2주차 - 그래프(DFS/BFS) 이론 정리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-2주차-그래프DFSBFS-이론-정리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)