［アルゴリズム］DFSとBFS

探索する。

大量のデータの中で欲しいデータを探すプロセス.
DFSやBFSなどを選択できます.
実際,DFSとBFSを理解するためには,基本的なデータ構造スタックとキュー,および再帰関数を理解する必要がある.
資料構造とは、データを表現、管理、処理するための構造を指す.
スタックとキューは、挿入と削除で構成されます.
(その他、オーバーフローや底流なども考慮すべき)

スタック

先入後出,後入先出構造をスタックと呼ぶ.
Pythonでは、個別のライブラリは必要ありませんが、appendメソッドとpopメソッドを使用すると、スタックと同じ操作になります.

キュー

前後に貫通する先入線出口群を指す.
Python実装ではCollectionsモジュールが提供するdeque資料構造を利用する.
append()、popleft()メソッドを使用します.
Dequeオブジェクトをリストデータ型に変更する場合はlist()メソッドを使用してリストデータ型を返します.

さいきかんすう

自分の関数を再呼び出しすることを再帰関数と呼ぶ.
無限反復なので、いつ終わるかの終了条件を必ず明確にしておきましょう.
再帰関数は内部的にスタック資料構造に似ている.

グラフ＃グラフ＃

グラフィックはノードノードノード(頂点Vertex)と直線Edgeで表されます.
グラフィックブラウズとは、1つのノードから複数のノードにアクセスすることです.
また、2つのノードが幹線で接続されている場合は、2つのノードが隣接していることを示します.
グラフは大体2つの方法で表現できます.

隣接行列:グラフィックの接続関係を2次元配列で表す.Pythonでは2次元リストとして実装され,接続されていないノード間では無限の費用で記述される.(99999999などの非常に大きな値に初期化)

INF = 9999999

garph = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

隣接リスト:グラフィックの接続関係をリストで表す.すべてのノードに関する情報を順番に接続して格納します.Pythonでは,隣接リストを2次元リストで表すことができる.

# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

二つの方式の違い

隣接マトリクスはすべての関係を格納し、ノードが多ければ多いほどメモリが浪費されます.逆に,隣接リスト方式は接続された情報のみを格納するため,メモリを効率的に使用できる.
しかし,隣接リスト方式はこれらの属性のため,特定の2つのノードが接続されているかどうかの情報を取得する速度が遅い.
したがって、特定のノードに関連するすべての隣接ノードを巡回する必要がある場合、隣接リスト方式は隣接マトリクス方式よりもメモリ領域が少ない.

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

DFSはDepth-First探索、深さ優先探索とも呼ばれ、図形の中で深部を優先的に探索するアルゴリズムである.(できるだけ遠いノードからブラウズを開始)N個のデータがあればO(N)の時間が必要となる.
また,スタックを用いたアルゴリズムであるため,実際の実装は再帰関数を用いた場合に非常に簡潔に実現できる.
BFSの意味はbreadth First Search,幅優先ナビゲーションである.簡単に言えば,近接ノードから探索を開始するアルゴリズムである.キューアルゴリズムを使用します.
同様に,データ数がNであればO(N)の時間が必要となる.一般的に、実際の実行時間はDFSよりも優れている.