[Python] BFS 알고리즘

💡 BFS

• BFS(Breadth First Search : 너비 우선 탐색) 알고리즘은 쉽게 말해 가까운 노드부터 탐색
• 큐 자료구조를 이용하는 것이 정석
• 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색 진행

💡 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

💡 파이썬 코드

from collections import deque

# BFS 알고리즘 구현
def bfs(graph, start, visited):

    queue = deque([start]) # 시작 노드 큐에 넣고 초기화
	visited[start] = True # 시작 노드 방문 표시
    
   # 큐가 비어있지 않은 동안 반복
	while queue:
        v = queue.popleft() # 큐에서 노드를 하나 꺼내 v에 할당
        print(v, end = ' ')
        
        # 현재 노드와 인접한 노드들에 대해 반복
        for i in graph[v]:
            if not visited[i]: # 해당 노드가 방문되지 않았다면
                queue.append(i) #  큐에 해당 노드를 추가
                visited[i] = True # 해당 노드 방문 표시
                
# 실제 그래프를 인접 리스트로 정의
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * (len(graph) + 1) # 방문 여부를 나타내는 리스트를 초기화
bfs(graph, 1, visited) # BFS 함수를 호출하여 시작 노드가 1일 때의 결과를 출력