[알고리즘] BFS

BFS

• 너비 우선 탐색
• 그래프 탐색 알고리즘 (그래프의 모든 정점을 확인하는 알고리즘) 중 하나
• 그래프 (Graph)
  • Vertex (정점) + Edge(간선)
  • Degree (차수) - 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합

• Queue를 이용하여 구현
• 최단경로를 구하는데 적합

시간 복잡도

• 인접 행렬 : O(n^2)
• 인접 리스트 : O(n+e)

자료 구조

• 검색할 그래프
• 방문 여부 확인 (재방문 금지)
• Queue

예시 코드

from collections import deque

def bfs(g,start,visited):
    queue = deque([start])
	visited[start] = True

	while queue:
		v = queue.popleft()
		print(v,end=' ')
		for i in g[v]:
			if not visited[i]:
				queue.append(i)
				visitied[i] = True