Algorithm_12(BFS)

BFS

그래프 종류

• DFS(깊이 우선 탐색)
• BFS(너비 우선 탐색)

BFS

• 탐색 시작점의 인접한 정점을 모두 방문 후, 방문했던 정점을 시작점으로 다시 인접한 정점 방문
• 인접한 정점들 탐색 후, 진행해야 하므로, 큐를 활용함

• BFS 구현 : 그래프 G와 탐색 시작점 V

def BFS(G, v, n) : # 그래프 G, 탐색 시작점 V
	visited = [0] * (n+1) 	# n: 정점의 개수
    queue = []				# 큐 생성
    queue.append(v)			# 시작점 v를 큐에 삽입
    while queue:			# queue가 비어있지 않은 경우
    	t = queue.pop(0)	# 큐의 첫 번째 원소 반환
        if not visited[t]:	# 방문되지 않은 곳이라면
        	visited[t] = True # 방문한 것으로 표시
            visit(t)			# 정점 t에서 할 일
            for i in G[t] :		# t와 연결된 모든 정점에 대해
            	if not visited[i] :	# 방문되지 않은 곳이라면
                	queue.append(i)	# queue에 삽입
                    visited[i] = visited[t] + 1 	# n으로 부터 1만큼 이동