그래프 - BFS

BFS(Breadth First Search)

큐를 사용한 너비 우선 탐색

1. 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드들을 모두 큐에 삽입 후 방문 처리

from collections import deque
q = deque()

def BFS(graph, v, visited):
	q.append(v)
    visited[v] = True
    while q:
    	v = q.popleft()
        print(v, end=" ")
    	for elem in graph[v]:
    		visited[elem] = True
        	q.append(elem)

#graph는 2차원 연결 리스트
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9

BFS(graph, 1, visited)