[알고리즘] DFS (깊이 우선 탐색)

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

대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색에 대해서 알아본다.

image-20201124175610412

DFS 구현 방법

A-B-D-E-F-C-G-H-I-J 가 된다. (BFS 알고리즘에서 최종 출력값이다.)

key valuess        
A B C      
B A D      
C A G H I  
D B E F    
E D        
F D        
G C        
H C        
I C J      
J I        
graph_list = {'A':(['B','C']),
              'B':(['A','D']),
              'C':(['A','G','H','I']),
              'D':(['B','E','F']),
              'E':(['D']),
              'F':(['D']),
              'G':(['C']),
              'H':(['C']),
              'I':(['C','J']),
              'J':(['I'])}

반복을 통한 DFS 알고리즘 코드

반복문(iteration)을 이용해 DFS를 구현한다.

from collections import deque 

def dfs(graph, start_node):

    visited= []
	need_visit = deque(start_node)
   
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited 

결과

start_node = 'A'
print(dfs(graph_list, start_node))
# ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

재귀(Recursion)를 활용한 DFS 알고리즘 코드

재귀(Recursion)을 이용해 DFS를 구현한다.

def recursive_dfs(graph, start_node, visited=[]):

    visited.append(start_node)
	
    for node in graph[start_node]:
    	if node not in visited:
            recursive_dfs(graph, node, visited)

    return visited

결과

start_node = 'A'
print(recursive_dfs(graph_list, start_node))
# ['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H', 'I', 'J']