Today I learned
2022/01/20
회고록
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
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)