dfs 순서 차이

def dfs1(graph, v, visited): # 1 2 7 6 8 3 4 5 -> 재귀,
# 그때 그떄 마다 매번 새로운 최선의 선택

  visited[v] = True
  print(v, end = ' ')

  for i in graph[v]:
    if not visited[i]:
      dfs1(graph, i, visited)
  
  return 0

def dfs2(graph, v, visited): # 1 2 7 6 3 4 5 8
# 대기 리스트(스택)에 들어있으면 방문하지 않는다
# 그래서 순서가 약간 다름
# 매번 새로운 최선의 선택이 아니라 약간 기준이 있달까

  stack = []
  stack.append(1)
  visited[1] = True

  while stack:
    now = stack.pop()
    print(now, end = ' ')
    for i in graph[now][::-1]:
      if not visited[i]:
        stack.append(i)
        visited[i] = True

  return 0

def dfs3(graph, v, visited): # 1 8 7 6 3 5 4 2

  stack = []
  stack.append(1)
  visited[1] = True
  
  while stack:
    now = stack.pop()
    print(now, end = ' ')
    for i in graph[now]:
      if not visited[i]:
        stack.append(i)
        visited[i] = True
    
  return 0


graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]


visited = [False] * 9
print('dfs1 rec')
dfs1(graph, 1, visited)
print('')

visited = [False] * 9
print('dfs2 stack-rev')
dfs2(graph, 1, visited)
print('')

visited = [False] * 9
print('dfs3 stack')
dfs3(graph, 1, visited)
print('')