TIL 9|DFSとBFS

TIL

苦痛のアルゴリズム、概念の壁、、、

グラフ＃グラフ＃

接続された頂点と頂点の関係を表すデータ構造.
ノード(Node):接続関係のあるデータごとに「頂点」(Vertex)と呼ばれます.
幹線(Edge):ノード間の関係を表示する線
隣接ノードれんぞくてん:幹線に直接接続されたノード(または頂点)幹線にちょくせつせつぞくされたノード(または頂点)

グラフィックの表示方法

隣接行列:図形の関連を2次元配列で表す

隣接マトリクスのadj[][]adj[i][j]:ノードiからノードjに幹線がある場合は1、そうでない場合は0

隣接リスト:リンクリストを使用してグラフィックの関連を表す

隣接リストでは、adj[]adj[i]:iの1番目のノードに接続されている要素のリスト

## 인접 행렬
# 2차원 리스트를 이용한 인접 행렬

graph = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
]
# 1을 True로 0을 False로 하기도 함

## 인접 리스트
# list in dictionary 를 이용한 인접 리스트
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

# list in list
graph = [
    [],
    [2, 5, 9],
    [1, 3],
    [2, 4],
    [3],
    [1, 6, 8],
    [5, 7],
    [6],
    [5],
    [1, 10],
    [9]
]

# list in dictionary 의 인접리스트가 key 값을 이용한다면 
# list in list 방식은 index 값을 이용

なぜDFSとBFSを使うのですか?その理由は全ての探索が必要だから、とにかくどこかが必要だから勉強したのだろう、、、怒るのは当然だが、落ち着いてじっくり観察しなければならない.

DFS (Depth First Search)

その名の通り、「深さ優先探索」です.
グラフィックで深部を優先的にブラウズするアルゴリズム.
1つの構造では、十分な探索を継続することができますが、継続できない場合は、別の方向で探索を再開します.
プロセスの実行:

ノードにアクセスし、深度隣接ノードに優先的にアクセス

このノードにアクセスし、深度隣接ノードに優先的にアクセス

終点に到着した場合は

に戻る
などなど.説明は多いが、醜いブドウの串の画像から見ると、理解が早い.
嫌いで見苦しいブドウの串
DFSは2つの方法で実現できる.
第一に、再帰関数
第二に、スタック
DFSの動作原理は基本的にスタック構造であり,通常は再帰関数を用いて実現される.

再帰関数による実装

1ルートノードから開始します.2現在アクセスしているノードをvisitedに追加します.3現在アクセスされているノードに隣接するノードでアクセスされていないノードにアクセスします.42から繰り返します.

# Q. 인접 리스트가 주어질 때, 모든 노드를 DFS 순서대로 방문하시오.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
  
visited = []

def dfs_recursion(adjacent_graph, cur_node, visited_array):
  visited_array.append(cur_node)
  for adjacent_node in adjacent_graph[cur_node]:
  	if adjacent_node not in visited_array:
  		dfs_recursion(adjacent_graph, adjacent_node, visited_array)  
  return visited_array

dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력!@!@!

スタック実装

1ナビゲーション開始ノードをスタックに挿入します.2現在のスタック内のノードを削除し、visitedに追加します.3スタックの最上位ノードにアクセスされていない隣接ノードがある場合は、スタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.43|を実行できなくなるまで繰り返します.

# Q. 인접 리스트가 주어질 때, 모든 노드를 DFS 순서대로 방문하시오.

graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
}

def dfs_stack(start_node, adjacent_graph):
    visited = []
    stack = [start_node]
    while stack:
	cur_node = stack.pop()
	visited.append(cur_node)
	for adjacent_node in adjacent_graph[cur_node]:
	    if adjacent_node not in visited:
		stack.append(adjacent_node)
    return visited

print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력!@@@@@@@!!!!!

ここで、「あ~dfsは再帰関数とスタックで実現できますよ~」と振り向くと、大きな失敗に遭遇し、問題を解く過程でアルゴリズムの親に挨拶する悲劇的な状況に遭遇します.
言い換えれば、DFSを解読する方法は2つある.そして….その2つの方法は異なる結果を示した.よく見ると、2つの方法で返される結果は違います.なぜこのような違いが現れたのでしょうか.
すなわち,最も深く探索する方式は同じであるが,実現方式と探索順序には差がある.

graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
}

再帰が隣接リストの小数からチェックされる場合、例えば1 -> [2, 5, 9]의 2 -> [1, 3]의 3 -> ...である.
スタック方式は1 -> [2, 5, 9]를 스택에 넣고 -> 9 -> [10]를 스택에...と同様であり、開始ノードに対応するすべての隣接リストをスタックに入れて起動するため、差が生じる.
2人ともDFSという点ではあまり意味がないと考えていますが、それを理解して近づくと、問題を解く過程で感情を消耗する残念な状況を避けることができます.

BFS (Breadth First Search)

BFSアルゴリズムは「幅優先探索」の意味を持つ.
簡単に言えば、最寄りのノードからナビゲートするアルゴリズム!!
最深部から探索したDFSとは異なり,隣接するすべてのノードを遍歴する.
醜いブドウで素早く観察してみましょう.

BFSの動作原理はキュー方式であるため,キューデータ構造を用いて実現できる.
操作方法:1ナビゲーション開始ノードをキューに挿入し、アクセス処理を行う.2ノードをキューから取り出し、そのノードのすべての隣接ノードからアクセスされていないノードをキューに挿入してアクセス処理を行う.
プロセスが再実行できなくなるまで、この手順32を繰り返します.

# Q. 인접 리스트가 주어질 때, 모든 노드를 BFS 순서대로 방문하시오.

import deque

graph = {
  1: [2, 3, 4],
  2: [1, 5],
  3: [1, 6, 7],
  4: [1, 8],
  5: [2, 9],
  6: [3, 10],
  7: [3],
  8: [4],
  9: [5],
  10: [6]
}


def bfs_queue(adj_graph, start_node):
  visited = []
  queue = deque[start_node]
  while queue:
      n = queue[0]
      visited.append(queue.leftpop())
      for adjacent_node in adj_graph[n]:
          if adjacent_node not in visited:
              queue.append(adjacent_node)
  return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력@!@!!@!@!!!

BFSの実装は.pop(0)を用いるため,内蔵関数dequeを用いて,時間的複雑さを考慮した効率的なコードを実現できる.