[알고리즘] BFS(Breadth-First Search)

📚 BFS (Breadth-First Search) 란?

 

한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 넓이 우선 검색을 적용한다.

 

DFS는 인접한 한 노드를 끝까지 탐색했다면 BFS는 인접한 모든 정점을 방문합니다.

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

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

 

처음에 넣은 노드이므로 큐를 이용해서 BFS를 구현할 수 있다.

📋 BFS 전체 과정

 

BFS의 알고리즘 방식을 설명하면 다음과 같다.

 

 

https://velog.io/@513sojin/C%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80BFS

 

1. 루트 노드를 큐에 넣는다
2. 현재 큐의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

 

📝 BFS 코드(feat : python)

 

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'D', 'E'],
    'C' : ['A', 'F', 'G'],
    'D' : ['B', 'H', 'I'],
    'E' : ['B', 'J'],
    'F' : ['C'],
    'G' : ['C'],
    'H' : ['D'],
    'I' : ['D'],
    'J' : ['E'],
}
# DFS와 비슷하다 그냥 스택을 쓰냐 큐를 쓰냐의 차이다.
# 1. 시작 노드를 큐에 넣습니다
# 2. 현재 큐의 노드를 빼서 visited 에 추가합니다
# 3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가한다.

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

    while queue:
        current_node = queue[0]
        del queue[0:1]
        visited.append(current_node)
        for value in adj_graph[current_node]:
            if value not in visited:
                queue.append(value)

    return visited

print(bfs_queue(graph, 'A'))  # 1 이 시작노드입니다!
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] 이 출력되어야 합니다.