DFS

DFS란?

• Depth First Search
  
  그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  
  특정 경로로 탐색을 하는 중 특정한 상황에서 최대한 깊숙하게 들어가 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘

<컴퓨터인터넷IT용어대사전>
자료의 검색, 트리나 그래프를 탐색하는 방법.
한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

스택 자료구조를 이용한다(FILO)

동작과정

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

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

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

# DFS 예시 (Python)
def dfs(graph, v, visited):
    visited[v] = True #현재 노드를 방문처리
    print(v, end=" ")
    for i in graph[v]:
        if not 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부터 시작
# out = 1 2 7 6 8 3 4 5