グラフへの深さ優先探索の実装
この演習では、グラフを走査する深さ優先探索アルゴリズムを実装します。
手順を確認しましょう。
- ランダムな頂点から開始する
- その頂点を訪問済み頂点リストに追加する
- 現在のノードに隣接する各頂点について
- 訪問済みの場合 -> 無視する
- 未訪問の場合 -> 再帰的に深さ優先探索を実行する
コードのテスト用に、次のグラフが辞書を使って読み込まれています。
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
演習の手順
current_vertexがまだ訪問されていないかどうかを確認してください。current_vertexをvisited_verticesに追加してください。- 適切な値を渡して、
dfs()を再帰的に呼び出してください。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def dfs(visited_vertices, graph, current_vertex):
# Check if current_vertex hasn't been visited yet
if current_vertex not in ____:
print(current_vertex)
# Add current_vertex to visited_vertices
____.add(____)
for adjacent_vertex in graph[current_vertex]:
# Call recursively with the appropriate values
____(____, ____, ____)
dfs(set(), graph, '0')