[알고리즘] 파이썬 DFS | 깊이 우선 탐색

 

DFS

- Depth first search

- 깊이 우선 탐색

- 그래프 자료에서 데이터를 탐색하는 알고리즘

 

 

 

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']

 

 

핵심

 

방문이 필요한 노드와 방문한 노드 분리

 

 

구현 코드

 

stack 구현

 

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)
            need_visited.extend(graph[node])
    return visited

 

 

 

deque 구현

 

from collections import deque

def dfs_self2(graph, start_node):
    need_visited, visited = deque(), deque()
    need_visited.append(start_node)

    while need_visited:
        node = need_visited.pop()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
    
    return visited

 

 

재귀 함수 구현

 

def recursive_self(graph, start, visited = []):
    visited.append(start)
    for node in graph[start]:
        if node not in visited:
            recursive_self(graph, node, visited)
    return visited

 

 

[출처] https://data-marketing-bk.tistory.com/44