幅優先探索

グラフや木構造において、現在のノードに隣接する全てのノードを先に探索してから次の深さに進む探索アルゴリズム。キューを使って実装される。最短経路の探索に適する。BFSと略される。

グラフや木構造を探索する際、可能な限り深い方向に進み、行き止まりになったら戻って別の枝を探索するアルゴリズム。スタック（再帰呼出し）を用いて実装される。迷路探索やトポロジカルソートに利用。

重み付きグラフにおける単一始点最短経路を求めるアルゴリズム。始点から各頂点への暫定最短距離を管理し、最小の頂点を確定させながら隣接頂点の距離を更新する。負の重みには対応できない。優先度付きキューで効率化可能。

頂点（ノード）と辺（エッジ）からなるグラフ構造を扱う数学分野。無向グラフ、有向グラフ、重みつきグラフ、完全グラフなどの種類があり、ネットワーク設計、最短経路問題、スケジューリングなどに応用される。

最適化問題を部分問題に分割し、各部分問題の最適解を記憶して再利用することで全体の最適解を効率的に求める手法。ナップサック問題や最短経路問題などに適用され、メモ化再帰やボトムアップ方式で実装される。

アルゴリズムの実行に必要な時間や空間の量をオーダー記号O(n)で表現したもの。時間計算量と領域計算量があり、入力サイズnに対する増加傾向でアルゴリズムの効率を評価する。O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(2^n)の順に計算量が大きい。

ピボット要素を選び、それより小さい要素と大きい要素に分割して再帰的に整列するアルゴリズム。平均計算量はO(n log n)だが最悪はO(n^2)。実用的には最速のソートアルゴリズムの一つで、多くの言語の標準ライブラリで採用。