[PS] BFS 개념 및 파이썬 코드

그래프는 노드(Node) 와 간선(Edge)로 표현되며 노드를 정점(Vertex) 라고 말한다.

 

그래프 탐색은 하나의 노드를 시작으로 모든 노드를 방문하는 것을 말하고, 두 노드가 간선으로 연결 되어 있다면, 두 노드는 인접(Adjacent)하다고 한다.

---

너비 우선 탐색(BFS)

너비 우선 탐색은 Breadth First Search 로 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.

 

BFS 에서 노드 탐색 순서는 아래와 같다.

BFS

이름에서도 알 수 있듯이 깊이가 얕은 노드부터 모두 탐색한뒤 깊이가 깊은 노드를 탐색하는 방법이다.

---

특징

- 두 노드 사이의 최단경로(Shortest Path)를 탐색할 때 활용하기 좋은 방식이다.

- 선입선출의 특징을 가지고 있는 자료구조인 큐를 활용하여 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색을 진행한다.

---

구현 알고리즘

1. 루트노드에서 탐색을 시작한다.

2. 루트노드와 인접하고 방문하지 않았고, 큐에 저장되지 않은 노드를 Queue에 넣는다.

3. Queue에서 pop하여 가장 먼저 큐에 저장한 노드를 방문한다.

 

순서는 아래와 같다.

(출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html)

BFS 알고리즘

위의 설명과 같이 루트노드에 먼저 방문하고(1), 인접하고 방문된적 없으며 큐에 저장되지 않은 노드를 큐에 저장하고 가장 먼저 큐에 저장된 노드로 이동해서 인접노드들의 조건을 확인한다. 이 방식을 큐에 저장된 노드가 모두 사라질때까지 반복한다.

---

그래프 구현 방식

코드로 이를 구현 하기 위해서는 DFS와 마찬가지로 2가지 방법이 있다.

1. 인접 행렬

2. 인접 리스트

위와 같은 그래프를 인접행렬과 인접 리스트로 표현해보자.

 

인접행렬

인접행렬은 2차원 배열에 각 노드가 연결된 형태를 boolean 값(true, false)을 이용하여 기록하는 방식이다.

인접행렬

인접리스트

인접리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식이다.

파이썬 에서는 기본 자료형은 리스트 자료형에 append()를 통해서 구현 할 수 있다.

인접리스트

---

구현코드

인접행렬

from collections import deque

def bfs(node):
    global is_visited, visit_arr, queue, graph, node_num
    
    # 노드 방문 처리
    is_visited[node] = True
    visit_arr.append(node)
    
    # 모든 인접 노드 검사 (1부터 node_num까지)
    for i in range(1, node_num + 1):
        # 인접하고, 방문하지 않았고, 큐에 없는 경우
        if graph[node][i] == 1 and not is_visited[i] and i not in queue:
            queue.append(i)
    
    # 큐에 남은 노드 처리
    if queue:
        next_node = queue.popleft()
        bfs(next_node)

 

인접행렬 배열을 graph, 방문여부 배열을 is_visited, 방문한 노드를 순서대로 저장하는 배열을 visit_arr 이라고 하면 위와 같이 코드를 작성 할 수 있고 시간 복잡도는 O(N^2) 가 된다.

# 예제 데이터 초기화
node_num = 5  # 총 노드 수 (예시)
graph = [      # 인접 행렬 (1-based)
    [0, 0, 0, 0, 0, 0],  # 0번 인덱스 더미
    [0, 0, 1, 1, 0, 0],  # 1번 노드
    [0, 1, 0, 0, 1, 0],  # 2번 노드
    [0, 1, 0, 0, 1, 1],  # 3번 노드
    [0, 0, 1, 1, 0, 1],  # 4번 노드
    [0, 0, 0, 1, 1, 0]   # 5번 노드
]
is_visited = [False] * (node_num + 1)  # 방문 여부
visit_arr = []                         # 방문 순서 기록
queue = deque()                            # BFS 큐

# BFS 실행 (시작 노드: 1)
bfs(1)
print("BFS 방문 순서:", BFS_visit_arr)

 

 

사용 예시는 위와 같다.

 

인접리스트

from collections import deque

def bfs(node):
    global is_visited, visit_arr, queue, graph
    
    # 현재 노드 방문 처리
    is_visited[node] = True
    visit_arr.append(node)
    
    # 인접 노드 순회
    for adj_node in graph[node]:
        # 방문하지 않았고, 큐에 없는 노드만 추가
        if not is_visited[adj_node] and adj_node not in queue:
            queue.append(adj_node)
    
    # 큐에 남은 노드 처리 (BFS 순서 유지)
    if queue:
        next_node = queue.popleft()
        bfs(next_node)

 

인접 행렬과 똑같이 인접리스트 배열을 graph, 방문여부 배열을 is_visited, 방문한 노드를 순서대로 저장하는 배열을 visit_arr 이라고 하면 위와 같이 구현할 수 있고 시간 복잡도는 O(N + E) 가 된다.

 

# 예제 데이터 초기화
graph = {
    1: [2, 3],    # 노드 1의 인접 노드
    2: [4],       # 노드 2의 인접 노드
    3: [5],       # 노드 3의 인접 노드
    4: [],        # 노드 4의 인접 노드
    5: []         # 노드 5의 인접 노드
}

is_visited = [False] * 6  # 노드 개수 + 1 (1-based)
visit_arr = []
queue = deque()  # BFS 큐

# BFS 실행 (시작 노드: 1)
bfs(1)
print("BFS 방문 순서:", BFS_visit_arr)  # 출력: [1, 2, 3, 4, 5]

 

예시는 위와 같다.