幅優先探索

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

グラフや木で、出発点に近い頂点から順に、同じ深さの頂点をすべて訪問してから次の深さへ進む探索方法。キューを使って実現し、辺に重みがない場合の最短経路を求められる。

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

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

グラフ上の2点間で、辺の重みの合計が最小になる経路を求める処理。カーナビの経路案内やネットワークのルーティングに使われる。代表的な解法にダイクストラ法やベルマンフォード法がある。

最短経路を求めるアルゴリズムの一つ。すべての辺について距離の更新を繰り返す。ダイクストラ法より遅いが、重みが負の辺を含むグラフでも扱え、負の閉路があることも検出できる。

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

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