파이썬 알고리즘 - DFS, BFS

DFS(깊이 우선 탐색)

def dfs(graph, v, visited):
  # 현재 노드를 방문처리
  visited[v]=True
  print(v,end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
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)
# 1 2 7 6 8 3 4 5

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

# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]
# 각 노드가 방문한 정보를 표현

bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6