말하는 감자

너비 우선 탐색 각 정점을 방문할 때마다 모든 인접 정점들을 검사하는 알고리즘이다. 처음 보는 정점이 있다면 방문예정이라고 표시하고 별도의 위치에 저장한다. 인접한 정점들을 모두 검사하고 나면, 목록에서 다음 정점을 꺼내어 방문하게 된다. 이 목록은 FIFO의 큐형태를 지니게 될 것이다. 한가지 특징은 모든 정점을 탐색할 수 있다는 것이다. 알고리즘의 큰 틀 # 슈도 코드 # 인접 리스트 or 인접 행렬 adj = [] # 발견 리스트 - false 로 초기화 discovered = [] # 방문 예정 큐 que = deque() def bfs(start): # 1. 시작점을 발견하고 방문 예정에 푸쉬한다. discovered[start] = True que.append(start) # 2. 방문 예정 ..