반응형
* DFS
def dfs(graph, v, visited):
visited[v] = True
print(v)
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [ False for i in range(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)
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 for i in range(9) ]
bfs(graph, 1, visited)
반응형
'Algorithm > 알고리즘 스터디(2021.12)' 카테고리의 다른 글
[Algorithm] 다익스트라 최단 경로 알고리즘 (0) | 2022.03.13 |
---|---|
[이코테] 4. 정렬 알고리즘 (0) | 2022.02.14 |
[이코테] dfs & bfs 문제풀이 (0) | 2022.02.08 |
[이코테] 구현: 시뮬레이션과 완전탐색 (0) | 2022.01.04 |
[이것이코딩테스트다][MEMO] 10, 11강, 12강, 13강 (0) | 2021.12.20 |