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

깊이 우선 탐색(Depth-First Search)

- 그래프 탐색 방법 중 한 가지 종류

 

"그래프 탐색은 BFS로 하는 것이 훨씬 쉽지만, 재귀함수 사용(백 트래킹에서 쓰임)을 익히기 위해서 DFS가 용이"

Stack 사용

 

 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

 

 

 

아이디어

- 시작점에 연결된 Vertex 찾기

- 찾은 Vertex를 계속해서 찾음(끝날 때까지)

- 더이상 연결된 Vertex가 없을 경우 다음으로 넘어감

 

 

 

---

[그래프 예시]

 

 

 

 

 

파이썬으로 구현한 DFS 알고리즘

# 재귀함수로 구현한 DFS

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

    for i in graph[start]:
        if visited[i] == False:
            dfs(graph, i, visited)
  
 # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],       # 처음 v가 1이기 때문에 빈 리스트 하나 넣어줌
  [2, 3, 8], 
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) - 0부터 시작하기 때문에 9개 곱하기
visited = [False] * 9

# 정의된 BFS 함수 호출
dfs(graph, 1, visited)

*** Stack을 사용해서 DFS 구현하기 시도 중