DFS & BFS

13321 ワード
大学生。 アルゴリズム#アルゴリズム# テキストリンク

「参照」(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)
    C言語ポインタの高度な操作
    明日学習キャンプ10日目TIL