DFS μκ³ λ¦¬μ¦μ λ¨Ό λ ΈλλΆν° νμνλ μκ³ λ¦¬μ¦μ΄λ©°, νμ μ μΆ λ°©μμΈ μ€ν μλ£κ΅¬μ‘°λ₯Ό μ¬μ©νλ€.
def dfs(graph, v, visited):
# νμ¬ λ
Έλλ₯Ό λ°©λ¬Έμ²λ¦¬
visited[v] = True
print(visited)
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 1
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS μκ³ λ¦¬μ¦μ κ°κΉμ΄ λ ΈλλΆν° νμνλ μκ³ λ¦¬μ¦μ΄λ©°, μ μ μ μΆ λ°©μμΈ ν μλ£κ΅¬μ‘°λ₯Ό μ¬μ©νλ€.
from collections import deque
def bfs(graph, start, visited):
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
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)
DFS | BFS | |
---|---|---|
λμ μ리 | μ€ν | ν |
ꡬν λ°©λ² | μ¬κ· ν¨μ μ΄μ© | ν μλ£κ΅¬μ‘° μ΄μ© |