幅優先検索
1403 ワード
1.概念
頂点と同じレベルのノード(兄弟ノード)を最初に参照する方法
->Pythonが提供するディレクトリとリストの資料構造を利用してグラフを表現できます.
コード#コード#
グラフィックの作成
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
アルゴリズム実装def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
Reference
この問題について(幅優先検索), 我々は、より多くの情報をここで見つけました https://velog.io/@wnsgur9701/너비-우선-탐색Breadth-First-Searchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol