BFS(너비우선탐색)

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

 

BFS란 한국말론 너비우선 탐색(Breadth First Search)이다.

 

너비우선탐색은 무엇인가.. 깊이와 반대다...

 

무언가 탐색을 할때 추가된 노드를 우선적으로 탐색하는것이 아니라 이미 추가되어있는 노드를 우선적으로 탐색하는 것..

 

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

 

이미지로...... (DFS와 동일한 노드)

 

 

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

 

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

 

대충 느낌이 팍 오죠?

 

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

 

DFS의 경우 추가된 노드를 우선적으로 순회했지만.. 이번에는 이미 추가되어있는 노드를 우선적으로 순회한다.

 

즉 Queue 구조를 참고하면 된다..!!

 

코드 ㄱㄱ

 

def bfs(graph, start_node):
    visit = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.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(bfs(graph, 'A'))


Output:
['A', 'B', 'C', 'H', 'D', 'I', 'J', 'M', 'E', 'G', 'K', 'F', 'L']

 

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