BFS로 그래프 정점 찾기

이번 연습 문제에서는 그래프 안에서 주어진 정점을 탐색하도록 BFS 알고리즘을 수정해 볼 거예요.

코드를 테스트할 수 있도록, 아래 그래프가 딕셔너리로 로드되어 있어요.

Graphical representation of a graph.

graph = {
  '4' : ['6','7'],
  '6' : ['4', '7', '8'],
  '7' : ['4', '6', '9'],
  '8' : ['6', '9'],
  '9' : ['7', '8']
}

이 연습은 강의의 일부입니다

Python으로 배우는 자료구조와 알고리즘

강의 보기

연습 안내

탐색 값을 찾았는지 확인하세요.
탐색 값을 찾았다면 True를 반환하세요.
for 루프 안에서 인접 정점이 방문되었는지 확인하세요.
탐색 값을 찾지 못했다면 False를 반환하세요.

실습형 인터랙티브 연습

이 예제를 이 샘플 코드를 완성하여 풀어보세요.

import queue

def bfs(graph, initial_vertex, search_value):
  visited_vertices = []
  bfs_queue = queue.SimpleQueue()
  visited_vertices.append(initial_vertex)
  bfs_queue.put(initial_vertex)

  while not bfs_queue.empty():
    current_vertex = bfs_queue.get()
    # Check if you found the search value
    if ____:
      # Return True if you find the search value
      ____    
    for adjacent_vertex in graph[current_vertex]:
      # Check if the adjacent vertex has been visited
      if adjacent_vertex not in ____:
        visited_vertices.append(adjacent_vertex)
        bfs_queue.put(adjacent_vertex)
  # Return False if you didn't find the search value
  ____

print(bfs(graph, '4', '8'))

코드 편집 및 실행