DFS-Python(파이썬)

DFS 개념

DFS란 Depth First Search의 약자로 "그래프 자료에서 데이터를 탐색하는 알고리즘" 이다

 

A부터 J까지 노드가 연결되어 있는 그래프 자료에서 특정 노드를 찾으려고 할 때 위에서 아래로 찾는 방식을 DFS라고 부른다.

 

위에서 아래로 탐색시 왼쪽으로 가냐 오른쪽으로 가냐는 시간 복잡도에 전혀 상관이 없다.

 

파이썬은 딕셔너리를 사용하여 그래프를 만든다. 다음 코드는 위 사진과 같은 그래프를 만드는 코드이다.

 

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

★DFS 기본 원칙

DFS에서 데이터를 찾을 때에 항상 기억해야하는 원칙이 있다

"앞으로 찾아 가야할 노드" 와 "이미 방문한 노드"를 기준으로 데이터를 탐색한다.

 

특정 노드가 "앞으로 찾아 가야할 노드"라면 계속 검색을 진행하고, "이미 방문한 노드"면 무시하거나 따로 저장하면 된다.

 

DFS 구현 방식

구현 방식에는 스택/큐를 활용하는 방식과 재귀함수를 통해 구현하는 방식 2가지가 존재한다.

 

1. 리스트를 활용한 DFS 구현

def dfs(graph, start_node):
 
    ## 기본은 항상 두개의 리스트를 별도로 관리해주는 것
    need_visited, visited = list(), list()
 
    ## 시작 노드를 지정하기
    need_visited.append(start_node)
    
    ## 만약 아직도 방문이 필요한 노드가 있다면,
    while need_visited:
 
        ## 그 중에서 가장 마지막 데이터를 추출 (스택 구조의 활용)
        node = need_visited.pop()
        
        ## 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
 
            ## 방문한 목록에 추가하기 
            visited.append(node)


            ## 그 노드에 연결된 노드를 추가, 리스트의 추가이기에 extend 사용
            need_visited.extend(graph[node])
            
    return visited

 

need_visited에서 추가된 Node들 중에서 가장 끝에 있는 것을 뽑아서 검색하는 방식이다.

pop을 활용하기에 성능면에서 떨어진다.

 

2. deque를 활용한 DFS 구현

def dfs2(graph, start_node):

    ## deque 패키지 불러오기
    from collections import deque
    visited = []
    need_visited = deque()

    ##시작 노드 설정해주기
    need_visited.append(start_node)

    ## 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:

        ## 시작 노드를 지정하고
        node = need_visited.popleft()

        ##만약 방문한 리스트에 없다면
        if node not in visited:

            ## 방문 리스트에 노드를 추가
            visited.append(node)

            ## 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])
                
    return visited

collections 패키지에서 deque를 활용한 코드이다. 리스트를 사용한 코드와 구조는 동일하다. 성능면에서 리스트보단 좋다.

 

3. 재귀함수를 통한 DFS 구현

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐
    visited.append(start)
    ##자식 노드를 탐색하는 반복문
    for node in graph[start]:
    	##자식 노드가 방문한 노드가 아니라면 노드 기준으로 함수 재귀
        if node not in visited:
            dfs_recursive(graph, node, visited)
            
    return visited

 

 

visited 자료형을 기본 함수 인자로 포함시키고, 방문한 리스트들을 재귀함수를 통해서 계속 visited에 담는 방식이다.

 

사람마다 코드가 조금씩은 다를 수 있지만, 기본적인 토대는

 

1) 리스트에 시작 노드 추가

2) 반복문을 통해 node를 방문하지 않았다면 다시 node를 시작 노드로 사용하는 재귀 사용

 

이라는 형태로 생각하면 될 것 같다.

 

제일 확실한 것은 어떤 그래프를 보고 DFS로 탐색시 어떤 결과가 나오는지 생각하고 코드를 이해하는게 중요한 것 같다.