[アルゴリズム]DFS(深度優先ナビゲーション)
2224 ワード
🧐 DFSとは?
🎈 DFSメソッド
DFSは以下の簡単なアルゴリズムに従って動作する.
最初の開始ノードをスタックに挿入します.(赤で表示されているノードはアクセスされているノードです)
スタック内の最上位ノードは(1)であるため、隣接ノードにアクセスされていない(2)ノードを入れる.
その後、ノード(2)の隣接ノードのうちアクセスされていないノード(3)をスタックに入れる.
ノード(3)の隣接ノードで、アクセスされていないノード(6)をスタックに入れる.
ノード(6)の隣接ノードには、アクセスされていないノード(7)がスタックに挿入される.
ノード(7)、(6)、(3)は、隣接するすべてのノードにアクセスするためにスタックを終了する.後でノード(2)を表示する場合、隣接ノード(4)にアクセスしないため、ノード(4)をスタックに入れる.
ノード(4)の隣接ノード(5)がスタックに入る.その後、スタックからノードを1つずつ飛び出します.
したがって、アクセスパスは1−2−3−6−7−4−5である.
🎈 DFSコード(Python)
# 방향이 있는 유향그래프
graph_list = {1: set([3, 4]),
2: set([3, 4, 5]),
3: set([1, 5]),
4: set([1]),
5: set([2, 6]),
6: set([3, 5])}
root_node = 1# DFS
def DFS_with_adj_list(graph, root):
visited = []
stack = [root]
while stack:
n = stack.pop()
if n not in visited:
visited.append(n)
stack += graph[n]-set(visited)
return visited
print(DFS_with_adj_list, root_node))画像注記:WikimediaCommons
Reference
この問題について([アルゴリズム]DFS(深度優先ナビゲーション)), 我々は、より多くの情報をここで見つけました https://velog.io/@tanger2ne/알고리즘-DFS깊이우선탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol