[アルゴリズム]DFS(深度優先ナビゲーション)

🧐 DFSとは?

Depth First Search

ナビゲーションアルゴリズム

準備:Stack(LIFO)

スタックを必要とすることなく実施できる(コンピュータは構造的にスタック原理を常に使用するため)

.

🎈 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))

以上は、https://blog.naver.com/ndb796/221230944971を参照して作成したものです.
画像注記:WikimediaCommons