DFS(깊이우선탐색)

이번엔 DFS를 알아보도록하자.

 

DFS란 한국말론 깊이우선 탐색(Depth First Search)이다.

 

깊이우선탐색은 무엇인가..

 

무언가 탐색을 할때 동일한 레벨의 노드를 탐색을 먼저 하는것이 아니라 아랫레벨의 노드를 우선 탐색하는 시스템이다.

 

역시 말로는 이해가 안가니...

 

이미지로......

 

 

사진과 같은 트리가 존재할때 깊이우선의 경우에 이렇게 순회하게된다.(우측, 좌측의 순서는 없음)

 

A -> B -> H -> M -> J -> K -> L -> I -> C -> D -> G -> E -> F

 

대충 느낌이 팍 오죠?

 

그럼 어떤식으로 구현하면 될지 생각을 해보면...

 

stack 구조를 이용해서 노드를 추가한 후 추가한 노드를 다시 탐색하고 추가한 노드를 다시 탐색하고 하면 깊이 우선이 가능!!!!

 

코드 ㄱㄱ

 

def dfs(graph, start_node):
    visit = list()
    stack = list()

    stack.append(start_node)

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

    return visit


if __name__ == "__main__":
    graph = {
        'A': ['B'],
        'B': ['A', 'C', 'H'],
        'C': ['B', 'D'],
        'D': ['C', 'E', 'G'],
        'E': ['D', 'F'],
        'F': ['E'],
        'G': ['D'],
        'H': ['B', 'I', 'J', 'M'],
        'I': ['H'],
        'J': ['H', 'K'],
        'K': ['J', 'L'],
        'L': ['K'],
        'M': ['H']
    }

    print(dfs(graph, 'A'))
    
    Output:
    ['A', 'B', 'H', 'M', 'J', 'K', 'L', 'I', 'C', 'D', 'G', 'E', 'F']

 

위에서 생각한거처럼 딱 나왔습니다..!!