DFS & BFS

「参照」(Search)

複数のデータから必要なデータを検索するプロセス

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

DFS, BFS

▶貴重な関数

独自の関数を再呼び出し

いつ終了するかは、無限コールを防止するために終了条件を必ず明記してください.

再帰関数の実行は、スタックデータ構造を使用して呼び出された関数によって行われ、前の関数呼び出しを終了する必要があります.

💨 グラフィック表現

隣接マトリクス:グラフィックの接続関係を2 D配列で表す

INF = 9999999999 # 무한의 비용

gragh = {
	[0, 7, 5],
    	[7, 0, INF],
    	[5, INF, 0] }

すべての関係を格納するノード数が多いほど、メモリが浪費されます.
隣接リスト:グラフの接続関係をリストで表す方法

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

接続された情報のみを使用してメモリを効率的に使用

✅ DFS

深度優先ビューグラフィックにおける深度優先ビューのアルゴリズム

特定のパスをナビゲートし、特定の状況でできるだけノードに深くアクセスし、別のパスに戻るアルゴリズム.

再帰関数の使用

📌 探索コース

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

スタックの最上位ノードにアクセスされていない隣接ノードがある場合は、スタックに格納してアクセス処理を行います.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.

続行できないまで手順2を繰り返します

def dfs(graph, v, visited):
	#현재 노드를 방문 처리
    visited[v] = True
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
graph = [
     [],
     [2, 3, 8],
     [1, 7],
     [1, 4, 5],
     [3, 5],
     [3, 4],
     [7],
     [2, 6, 8],
     [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

✅ BFS

幅優先検索隣接ノードから検索を開始するアルゴリズム

通常はキューデータ構造を使用します

📌 探索コース

ナビゲーションの開始ノードをキューに挿入し、アクセスを処理

キューからノードを取り出し、そのノードの隣接するすべてのノードからアクセスされていないノードをキューに挿入してアクセス処理します.

続行できないまで手順2を繰り返します

def bfs(graph, v, visited):
	#현재 노드를 방문 처리
    queue = deque([start])
    
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
            
graph = [
     [],
     [2, 3, 8],
     [1, 7],
     [1, 4, 5],
     [3, 5],
     [3, 4],
     [7],
     [2, 6, 8],
     [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)