DFS 기본 구현

DFS (Depth First Search) :
  - 노드에 연결된 자식들을 탐색하고 그와 연결된 노드들을 탐색하는 기법
* visited 큐와 need_visit 스택을 사용
* 시간 복잡도: O(N+E) (N: 노드 수, E: 간선 수) 

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']
"""
{
    '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']
}
"""

def dfs(graph, start_node):
    visited = list()
    need_visit = list()

    need_visit.append(start_node)

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

    return visited

print(dfs(graph, 'A')) 

""" ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E'] """

출처 : FASTCAMPUS