DFS

# 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)

# 각 노드가 연결된 정보를 리슽느 자료형으로 표현(2차원 리스트)
graph = [
  [], # node 0
  [2,3,8], # node 1
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7] # node 8
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

dfs(graph,1,visited)

DFS(깊이 우선 탐색)

graph = 2차원 배열로 그래프 정의

visited = 해당노드의 방문여부

v(해당선택노드)	i(해당 노드의 인접)	visited(인접 노드의 방문여부)	print
1	2,3,8	False, False, False	1
2	1,7	True,False	2
7	2,6,8	True,False,False	7
6	7	True	6
8	1,7	True,True	8
3	1,4,5	True,False,False	3
4	3,5	True, False	4
5	3,4	True,True	5

방문 순서 1 - 2 - 7 - 6 - 8 - 3 - 4 -5

DFS를 재귀적으로 구현했습니다.