Python BFS(Breadth-First Search)

코딩테스트 연습 BFS

[이것이 취업을 위한 코딩테스트다 with 파이썬]을 기반으로 작성하였습니다.

BFS = Breadth-First Search 로 큐 자료구조에 기초한다. DFS와 마찬가지로 O(N)의 시간이 소요된다. 일반적인 수행시간은 DFS보다 좋은 편이다.

알고리즘

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

from collections import deque

#BFS method 정의
def bfs(graph, start, visited):
  # queue 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # queue가 빌 때까지 반복
  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]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 홤수 호출
bfs(graph, 1, visited)

결과

1 2 3 8 7 4 5 6