DFS(Depth-First-Search) | 깊이우선 탐색이란 무엇인가요? - 1분 정리

DFS는 그래프의 깊은 부분을 탐색하는 알고리즘이다. 여기서 "탐색"이란 많은 양의 데이터 중에서 내가 원하는 데이터를 추출하는 과정을 의미한다.

 

 

깊이우선 탐색은 stack과 재귀함수를 이용하여 구현을 하며 다음과 같은 과정을 거치게 된다.

 

 

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

2. 스택에 삽입된 최상위 노드에 인접한 방문하지 않은 노드가 하나라도 있는 경우 방문처리를 한다. 인접한 노드 중 방문할 수 있는 노드가 없는 경우 스택을 꺼낸다.

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

 

 

dfs 그래프 예시

 

 

다음과 같은 그래프가 있다고 가정을 해보다 dfs 방식으로 노드를 탐색을 해보자! (방문기준 : 인덱스 번호가 낮은 순서부터 진행을 한다.)

 

 

 

 

 시작 노드인 1을 스택에 삽입을 하고 방문처리를 한다. 그 후 스택에 삽인 된 최상단 노드 중에 인접한 방문하지 않은 노드를 방문한다. 좀 어렵지만 곰곰이 생각을 해보자 8번 노드를 방문한 후 다음과 같은 결과가 나오게 된다. 

 

 

 

 

방문하지 않은 노드가 없을때까지 dfs를 반복하게 되면 1->2->7->6->8->3->4->5로 방문을 하게 된다. 파이썬 코드로 구현하게 되면 다음과 같다.

graph = [  #각 노드가 연결된 정보를 
  [], # 인덱스가 0인경우 말한다.
  [2,3,8],  #인덱스가 1
  [1,7],   #2
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False] * 9 #False라는 불리언 값이 9개를 만들었음

def dfs(graph,v,visited):
  visited[v] = True #방문을 했으면 방문처리를 한다.
  print(v)  #인덱스 숫자가 노드의 숫자와 같기에 인덱스 숫자를 그냥 출력을 하면 된다.
  for i in graph[v]:
    if visited[i] == False:
      dfs(graph,i,visited)
    
dfs(graph,1,visited)

 

 1->2->7->6->8->3->4->5  의 순서로 출력이 되는 것을 확인할 수 있다.