BFS 알고리즘 - 하나만 파지 말고 골고루 하는 건 어떨까요?

안녕하세요. 오늘은 기본적인 경로 계획 알고리즘인 BFS 알고리즘을 공부해보겠습니다!

글의 마지막에 예제 코드도 준비해뒀으니 끝까지 읽어주세요 :)

---

BFS 알고리즘이란

Breath First Seaech의 약자로 너비 우선 탐색이라고도 합니다.
BFS 알고리즘의 동작 방식을 간단히 설명드리면 갈 수 있는 모든 길을 가본 후에야 다음 단계로 나아가는 탐색법입니다.

 

BFS 알고리즘은 QUEUE를 이용해서 탐색해야 할 노드들을 관리하며 탐색한 노드는 탐색했다고 표시를 남깁니다.

이러면 중복 탐색이 이뤄지지 않고, 원하는 노드까지의 경로를 탐색할 수 있습니다.

 

BFS 알고리즘 pseudo code

pseudo code는 다음과 같습니다.

• 시작 노드와 연결된 모든 노드의 탐색을 하는 코드입니다.

def BFS(graph, start_node_id):
    queue = [graph.get_node(start_node_id)]
    while not queue.is_empty():
        node = queue.pop()
        if node.is_visited:
            continue
        graph.set_node_visited(node.id)
        queue.push(graph.get_connected_nodes(node.id))

 

이렇게 설명하니 너무 간단해보이는데 한번 그림과 같이 살펴볼까요?

예제 그래프 짜잔!

BFS 알고리즘을 이용해서 노드 1에서 노드6까지 탐색해보겠습니다.

탐색한 노드는 노란색으로 칠하고, 앞으로 탐색해야 할 노드는 QUEUE에 적어뒀습니다.

전반전

후반전

어떠세요? 그림으로 봐도 간단하죠?

 

BFS 알고리즘 예제 코드

from dataclasses import dataclass
from typing import List

@dataclass
class Node:
    id: int
    is_visited: bool = False

@dataclass
class Edge:
    start_node: Node
    end_node: Node

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node

@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]

    def set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [edge.get_other_node(node_id) for edge in adjacent_edges]

def BFS(graph: Graph, start_node_id: int):
    queue = [graph.get_node(start_node_id)]
    stage = 0

    while len(queue) > 0:
        stage += 1
        
        node = queue.pop(0)
        print("방문한 노드: {:d}".format(node.id))

        if node.is_visited:
            continue
        
        print()
        print("탐색 {:d}".format(stage))

        graph.set_node_visited(node.id)
        queue += graph.get_connected_nodes(node.id)

        print("QUEUE: ", [node.id for node in queue])





if __name__ == "__main__":
    nodes = {}
    for i in range(6):
        nodes[i+1] = Node(id=i+1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(start_node=nodes[1], end_node=nodes[2])]
    adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[3])]
    adjacent_edges[2] = [Edge(start_node=nodes[2], end_node=nodes[4])]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[5])]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[6])]
    adjacent_edges[3] = [Edge(start_node=nodes[3], end_node=nodes[4])]
    adjacent_edges[5] = [Edge(start_node=nodes[5], end_node=nodes[6])]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    BFS(graph, 1, 6)

실행 결과

짠!

 

알고리즘 복잡도

O(|V|+|E|)

(|V|는 전체 노드의 갯수, |E|는 전체 엣지의 갯수를 의미합니다.)

 

복잡도가 저렇게 나온 이유는 작성된 코드가 모든 노드를 순회하고, 엣지의 수만큼 queue에 노드를 추가하기 때문입니다.

 

---

BFS 알고리즘은 어떠셨나요?

앞으로 공부할 알고리즘들과 비교하면 그래도 이해하기 쉽고 구현하기도 쉬운 축에 속하는 것 같습니다.

더 공부하고 싶으신 내용이나 부족한 부분 알려주시면 보완하도록 하겠습니다.

감사합니다 👍