# dfs 기본 원칙
# 앞으로 찾아 가야할 노드와 이미 방문한 노드 기준으로 탐색
# 앞으로 찾아 가야할 노드면 계속 검색
# 이미 방문한 노드이면 무시하거나 따로 저장
# 구현 방식은 "스택/큐" or "재귀함수를 통해 구현"
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
def dfs (graph, start_node):
#두개의 리스트 별도로 관리
need_visited = []
visited = []
#시작 노드를 시정하기
need_visited.append(start_node)
#방문이 필요한 노드가 있다면
while need_visited:
# 가장 마지막 데이터를 추출 (스택 구조를 활용)
node = need_visited.pop()
# 만약 그 노드가 방문한 목록에 없다면
if node not in visited:
# 방문한 목록에 추가하기
visited.append(node)
# 그 노드에 연결된 노드를
need_visited.extend(graph[node])
return visited
#print(dfs(graph,'A'))
from collections import deque
def dfs2(graph, start_node):
visited = []
need_visited = deque()
##시작 노드 설정
need_visited.append(start_node)
##방문이 필요한 리스트가 아직 존재한다면
while need_visited:
##시작 노드를 지정하고
node = need_visited.pop()
#만약 방문한 리스트에 없다면
if node not in visited:
#방문 리스트에 노드를 추가
visited.append(node)
need_visited.extend(graph[node])
return visited
#print(dfs2(graph,'A'))
def dfs_recursive(graph, start,visited = []):
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
print(dfs_recursive(graph,'A'))