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

비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 이러한 탐색 방법에는 대표적으로 Depth First Search (깊이 우선 탐색) 그리고 Breadth First Search (너비 우선 탐색)이 있다.

 

우선 DFS 부터 알아보도록 하겠다.

 

1. DFS 로직

1. 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳 까지 깊이 탐색
2. 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
3. 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회
4. 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용한다

 

2. 스택을 사용한 DFS 알고리즘 설명

정점 v에 인접한 정점 중에서:

• 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문
  • w를 v로 하여 다시 1을 반복
• 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 1을 반복

# 코드로 보는 알고리즘 로직

visited = []
stack = []
DFS(v):
  v 방문
  visited[v] -> true
  do {
    if (v의 인접 정점 중 방문 안 한 w 찾기):
    	visited.push(v)
    while(w) {
      w 방문
      visited[w] -> true
      stack.push(w)
      v <- w
      v의 인접 정점 중 방문 안한 w 찾기
    }
    v <- stack.pop()
  } while(v):
end DFS()

 

3. Python으로 구현해보기

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}
 
def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for k in graph[node]:
            dfs(graph,k, visited)
    return visited
 
visited = dfs(graph1,'A', [])
print(visited)

>>> ['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']