포시코딩

BFS(Breadth First Search) - 너비 우선 탐색 본문

자료구조알고리즘/이론

BFS(Breadth First Search) - 너비 우선 탐색

포시 2022. 11. 29. 18:02
728x90

BFS란?

한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법.

더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다.

 

BFS 구현 방법

1. 큐

BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 

이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고

가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

-> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나

 

큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다.

코드로 직접 살펴보자

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}
# 1. 시작 노드를 큐에 넣는다.
# 2. 현재 큐의 노드를 빼서 visited에 추가
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가

def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []

    while queue:
        curr_node = queue.pop(0) # queue이기 때문에 앞에서부터 꺼낸다.
        visited.append(curr_node)
        for adj_node in adj_graph[curr_node]:
            if adj_node not in visited:
                queue.append(adj_node)
    return visited

print(bfs_queue(graph, 1))  # 1 이 시작노드
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야함
728x90

'자료구조알고리즘 > 이론' 카테고리의 다른 글

이중 for문의 시간복잡도  (0) 2022.12.12
동적 계획법(Dynamic Programming)  (0) 2022.11.29
DFS(Depth First Search) - 깊이 우선 탐색  (0) 2022.11.29
그래프(Graph)  (0) 2022.11.29
트리(Tree), 힙(Heap)  (0) 2022.11.28