DFS

• DFS

  • 깊이 우선 탐색 
  • stack(쌓는 것) 자료구조(재귀함수)를 이용함
  • stack은 파이썬에서 list를 이용하면 됨
  • append는 뒤에 붙이기
  • pop은 가장 최신으로 붙인 값을 빼기
  • list[::-1]는 최상단(마지막에 append한 순으로) 출력
  • 보통 번호가 낮은 인접 노드부터 방문함

• 그래프로 보기

그래프

• 그래프 DFS 풀이: 1→2→7→6→6에서 방문하지 않은 인접노드가 없음→다시 7로→8→3→4→5
• 코드로 해보기!

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 = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] #각 번호에 연결된 노드들
visited = [False]*9 #앞의 [] 포함해서 9개
dfs(graph,1,visited)