Algorithms-[DFS]

오늘은 DFS(Depth-First-Search) 깊이 우선 탐색에 대해서 공부하려고 한다.

DFS는 루트노드(혹은 임의의노드)에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하고 넘어가는 알고리즘을 뜩한다. 이 방법은 모든 노드를 탐색하려고 할 때 사용하며 BFS 너비우선탐색보다 간단하지만 모든 노드를 왔다갔다 하기 때문에 느리다. 이해하기 쉬운 비유로는 연속으로 된 갈림길이 있을 때 한방향으로 쭉가다가 막히면 바로 전 갈림길로 돌아와서 반대로 쭉가고 다시 돌아오고를 반복하는 것으로 이해 할 수 있다. 이렇게 계속 돌아오는 알고리즘이기 때문에 순환 알고리즘 즉 재귀함수의 형태를 띄고있다. 또한 스택을 사용하여 구현한다. 

출처:위키피디아

graph = {
    'a': ['b', 'c', 'e'],
    'b': ['a','d'],
    'c': ['a', 'e', 'f'],
    'd': ['b'],
    'e': ['a','c'],
    'f': ['c']
}

def dfs(graph, root_node):
    stack,visit = list(),list()
    stack.append(root_node)
    
    while stack:
    	node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(reversed(graph[node]))
            
    return visit