ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム
最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。
頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...
木の直径を求めるアルゴリズム
木に存在する2つノード間の最大距離を木の直径と言います。
重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。
重み無しの木の例：
以下は直径が5となる木の例で
ダイクストラ法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては
計算量が \(O(|E| \l ...ベルマンフォード法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、
負の辺が含まれているような場合でも適用 ...トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート）
トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。
左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。
閉路のないDAGグラフにおける橋(bridge)を検出するアルゴリズム
無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。
※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。（くわしくはグラフ ...
グラフにおける関節点(Articulation Points)を検出するアルゴリズム
連結グラフにおける関節点(切断点)とは、「グラフから取り除くと、グラフが非連結になってしまうような頂点」のことを言います。
※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があること ...
グラフ(Graph)のデータ構造と基本用語の定義
頂点(ノード)と、頂点同士の関係を表したデータ構造です。
数学的には、グラフは以下の２つから構成されます。
頂点（ノード）の集合頂点同士がつながっているか(隣接しているか)を表す、辺（エッジ）の集合 ...