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)


graph=[
  [], #인덱스 0은 비워둠
  [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, v, visited):
  q=deque([v]) #큐 생성
  visited[v]=True #방문처리
  while q: #큐가 비어있지 않은동안
    w = q.popleft() #큐의 front를 w에 저장하고 pop
    print(w,end=' ')
    for i in graph[w]:
      if not visited[i]:
        q.append(i)
        visited[i]=True
    
graph=[
  [], #인덱스 0은 비워둠 (안쓸거니까)
  [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)