BFS でグラフの頂点を見つける
この演習では、グラフ内で指定した頂点を探索するために、BFS アルゴリズムを改良します。
コードの動作確認に使えるよう、次のグラフが辞書で読み込まれています。
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'))