グラフに対するDFSの実装
この演習では、グラフを走査する depth first search アルゴリズムを実装します。
手順を思い出しましょう。
- 任意の頂点から開始する
- その頂点を訪問済みリストに追加する
- 現在のノードに隣接する各頂点について
- 訪問済みであれば -> 無視する
- 未訪問であれば -> 再帰的にDFSを実行する
コードのテストを助けるため、次のグラフが辞書で読み込まれています。
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')