幅優先探索を使った頂点の探索
この演習では、幅優先探索アルゴリズムを改修して、グラフ内の指定した頂点を探索できるようにします。
コードのテスト用に、以下のグラフが辞書を使って読み込まれています。
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'))