BFS

BFS - 너비 우선 탐색, 큐 자료구조에 기초한다

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐(Queue) 구현을 위해 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

graph = [
  [], # node 0
  [2, 3, 8], # node 1
  [1, 7], # node 2
  [1, 4, 5], #node 3
  [3, 5], # node 4
  [3, 4], # node 5
  [7], # node 6
  [2, 6, 8], # node 7
  [1, 7] # node 8
]

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

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

v(현재노드)	queue	출력
1	2,3,8	1
2	3,8,7	2
3	8,7,4,5	3
8	7,4,5	8
7	4,5,6	7
4	5,6	4
5	6	5
6		6

output : 1-2-3-8-7-4-5-6

 

-큐 자료구조에 기초한다는 점에서 구현이 간단하다. 일반적인 경우 수행 시간은 DFS보다 좋은 편이다.