DFS

p.142

 

DFS(Depth First Search) : 깊이 우선 탐색

* 스택을 사용 = 재귀 함수 사용

* graph를 인접 리스트 사용

* visited로 방문했는지 여부 확인

 

[동작 과정]

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리

                                방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼내기

3. 2번 과정을 스택에 남아있는게 없을 때까지 반복

(일반적으로 인접 노드 중 방문하지 않은 노드가 여러개 있을 시, 번호가 낮은 순서부터 처리)

 

 

def dfs(graph, v, visited):
  visited[v]=True
  print(v, end=' ')

  for i in graph[v]:
    if visited[i]==False:
      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

dfs(graph,1,visited)

 

[결과]

1 2 7 6 8 3 4 5