アルゴリズム理論-DFS

探索する

DFSとBFSの前に知っておいたほうがいいです。(詳細は後述)

1.スタック->後入先出(LIFO)

2.Q->先入先出(FIFO)一番早い資料。

3.再帰関数->独自の関数を再呼び出します。

DFS

オーダー

1.スタックにナビゲーション開始ノードを挿入し、アクセスを処理する

2.隣接ノードがスタックの最上位ノードにアクセスしていない場合は、スタックに入れてアクセス処理を行います。すべてにアクセスする場合は、上部ノードをポップアップします。

3.完了できないまで、2番目のプロセスを繰り返します。

上のノードのように,最小0−>1の順にアクセスし,1に隣接する3,4のうち3にアクセスする.3再アクセスができないので、アクセス処理後に出力し、4にアクセスします。0以外のすべて

# DFS 메서드 정의
def dfs(graph, v, visited):
	#현재 노드 방문 처리
    visited[v] = True
    print(v, end =' ')
    #현재 노드와 연결된 다른 노드 재귀로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
graph = [
    [],#보통 1부터 시작하므로 0은 빈 리스트를 넣어줌 
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#각 노드가 방문된 정보 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)