🌼 BFS(Breath-First-Search) Algorithm

🌼 BFS(Breath-First-Search) Algorithm

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.
  1. 탐색 노드를 큐에 삽입하고, 방문처리한다.
  2. 큐에서 노드를 꺼낸 후 해당 노드와 인접한 방문하지 않은 모든 노드를 큐에 삽입하고 방문처리한다.
  3. 2번 과정을 더 이상 할 수 없을때까지 반복한다.
• 사용되는 문제: 각 간선의 비용이 모두 동일한 상황에서 최단거리 찾는문제 등

🌼 구현 코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True

    # 큐다 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')

        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
            visited[i] = True


# 각 노드가 연결된 정보를 표현(2차원 배열)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 정의된 BFS 함수 호출
bfs(graph, 1, visited=[False] * 9)

# 실행 결과
# 1 2 3 8 7 4 5 6