プログラミング

ある旅路には N 個の停車駅があり、乗り物は駅 0 から出発して駅 N-1 まで進みます。すべての駅同士のペアに対する切符代(運賃)が表として与えられているとき、それらの運賃の中から組み合わせて、目的地に到達するための最小費用を求めます。たとえば、途中の駅を経由したほうが直行よりも安くなる場合があります。与えられた運賃表をもとに、最も安い移動経路を見つけるのがこの問題の目的です。入力と出力入力: 旅程のコスト行列 0 15 80 90 ∞ 0 40 50 ∞ ∞ 0 70 ∞ ∞ ∞ 0 出力: 最小費用は 65。 最初に駅 0 から駅 1 へ移動し(費用

重み付き有向グラフが与えられ、各頂点間の辺の重みがコスト行列として表されているとします。さらに、始点となる頂点 u と終点となる頂点 v、そして使用する辺の本数 k も与えられます。この課題は、ちょうど k 本の辺を使って頂点 u から頂点 v へ移動するときの最短距離を求めることです。問題のアプローチこの問題を解くには、始点 u から出発し、隣接するすべての頂点へ順に移動していきます。その際、再帰呼び出しのたびに残りの辺数 k を 1 ずつ減らしながら探索を進めることで、正確に k 本の辺を使う経路の中から最小のコストを見つけ出します。入力と出力Input: グラフのコスト行列 0 10 3

有向グラフにおいて、同じ成分内の任意の2つの頂点の間に、双方向への経路が存在するとき、そのグラフは「強連結（strongly connected）」であると言われます。このような頂点の集合を「強連結成分（Strongly Connected Component：SCC）」と呼びます。強連結成分を求める考え方この問題を解くためには、コラサジュのアルゴリズム（Kosarajus Algorithm）と呼ばれる手法がよく用いられます。手順は以下の通りです。まずDFS（深さ優先探索）を実行し、各頂点の「完了時刻（finish time）」を記録します。次に、元のグラフのすべての辺の向きを反転させた「転

蛇はしごゲームとは蛇はしごゲーム（Snakes and Ladders）は、世界中で親しまれている有名なボードゲームです。ボード上には番号が振られたマスが並んでおり、一部のマス同士は「はしご」または「ヘビ」によって接続されています。はしごのあるマスに止まれば、順番に進むことなく一気に上のマスへ移動でき、ゴールに大きく近づくことができます。一方、ヘビのいるマスに止まってしまうと、下のマスへ引き戻され、そこから再びスタートすることになります。本記事では、この問題に対してスタートからゴールまで到達するために必要な最小のサイコロ振り回数を求めるアルゴリズムを解説します。最短手数を求める場合、幅優先探索

タージャンのアルゴリズムとはタージャン(Tarjan)のアルゴリズムは、有向グラフの強連結成分(Strongly Connected Components: SCC)を効率的に求めるためのアルゴリズムです。最大の特徴は、深さ優先探索(DFS)をたった1回実行するだけで、すべての強連結成分を見つけられる点にあります。DFSによる探索を行うと、グラフから「DFS木」を構成できます。このDFS木をもとに強連結成分が判明します。ある部分木の根が検出された時点で、その部分木全体を出力することができ、この部分木こそが1つの強連結成分となるのです。アルゴリズムの鍵となる値disc[u]:頂点uがDFSによっ

トポロジカルソートとは トポロジカルソート（位相的整列）とは、有向非巡回グラフ（DAG：Directed Acyclic Graph）の頂点を線形順序に並べるアルゴリズムです。グラフ内のすべての辺 U → V に対して、並べた順序の中で頂点 u が必ず頂点 v より先に現れるように整列します。 始点側の頂点は終点側の頂点より先に処理される必要があるため、探索済みの頂点を一時的に保持するためにスタックを使用します。すべてのノードの処理が完了した後、スタックから要素を順に取り出して表示するだけで、トポロジカルな順序が得られます。 入力と出力 以下は、6つの頂点を持つグラフを隣接行列形式で入力し

フォード・ファルカーソン（Ford-Fulkerson）アルゴリズムは、与えられたグラフにおいて、始点（ソース）から終点（シンク）までの最大フロー（最大流）を求めるために用いられる古典的なアルゴリズムです。このグラフでは、すべての辺に「容量」が設定されており、ソースとシンクという2つの頂点が指定されます。ソース頂点は外向きの辺のみを持ち、シンク頂点は内向きの辺のみを持つという特徴があります。アルゴリズムが満たすべき制約条件各辺に流れるフローは、その辺に設定された容量を超えてはならない。ソースとシンクを除くすべての頂点において、流入するフローの合計と流出するフローの合計は等しくなければならない。

グラフにおける推移閉包（Transitive Closure）とは、ある頂点 u から別の頂点 v へ「到達できるかどうか」を示す到達可能性行列のことです。1つのグラフが与えられたとき、すべての頂点ペア (u, v) について、u から v が到達可能かどうかを求めます。 最終的に得られる行列はブール型（0 と 1 のみ）で構成されます。頂点 u から頂点 v に対応する要素が 1 である場合、「u から v へ至る経路が少なくとも 1 本存在する」ことを意味します。逆に 0 であれば、いかなる経路を通っても u から v には到達できないことを表します。 この手法は、隣接行列に対して動

グラフが与えられたとき、そのグラフがスターグラフ（star graph）であるかどうかを判定する問題について解説します。スターグラフとは、1つの中心頂点（ハブ）が他のすべての頂点に接続され、周辺の頂点同士は互いに接続されていない木構造の一種で、全体の形が星のように見えることからこの名前が付いています。 判定には、グラフを走査して「次数が1の頂点の個数」と「次数が n−1 の頂点の個数」を数えます（ここで n はグラフの頂点数です）。次数1の頂点が n−1 個存在し、かつ次数 n−1 の頂点がちょうど1個存在する場合、そのグラフはスターグラフであると判定できます。 入力と出力 入力（隣接行列

ベルマン・フォード法とはベルマン・フォード法（Bellman-Ford Algorithm）は、始点（ソース）頂点からグラフ内の他のすべての頂点への最短距離を求めるためのアルゴリズムです。同じく最短経路問題を解くダイクストラ法との最大の違いは、負の重み（負のコスト）を持つ辺の扱いです。ダイクストラ法では負の重みを含むグラフを正しく処理できませんが、ベルマン・フォード法では負の重みも簡単に扱えます。さらに、グラフ内に負の閉路（ネガティブサイクル）が存在するかどうかを検出できる点も大きな特徴です。ベルマン・フォード法はボトムアップ（下から上へ）のアプローチで距離を計算します。まず、パスに含まれる辺

この問題では、複数の異なる箱が与えられます。それぞれの箱は長さ・幅・高さが異なる場合があります。目的は、これらの箱を積み上げて、可能な限り高い塔を作ることです。箱は自由に回転できますが、守らなければならないルールが1つあります。 ある箱を別の箱の上に置けるのは、下の箱の上面の面積が、上の箱の底面の面積よりも大きい場合のみです。 入力と出力 入力: 箱のリストが与えられます。各箱は (長さ, 幅, 高さ) で表されます。 { (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) } 出力: 箱の積み上げの最大高さ: 60 アルゴリズム maxHeight(b

無向グラフの中にサイクル（閉路）が存在するかどうかを判定するには、DFS（深さ優先探索）によるグラフ走査を利用します。基本的な考え方は次のとおりです。訪問済みの各頂点 v について、隣接する頂点 u を発見したとき、その u がすでに訪問済みであり、かつ u が頂点 v の親ではない場合、そこにサイクルが存在すると判断できます。なお、本記事では説明を簡潔にするため、任意の2つの頂点間に平行辺（多重辺）は存在しないものと仮定します。入力と出力の例入力（隣接行列）: 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1

有向グラフのサイクル検出とは深さ優先探索（DFS）の走査アルゴリズムを利用すると、有向グラフ内のサイクル（閉路）を検出できます。あるノードに自己ループ（自分自身への辺）が存在する場合はそれがサイクルとみなされ、また、子ノードから親ノードへ戻る辺が存在する場合も同様にサイクルと判定されます。グラフが非連結（分断されたグラフ）の場合、複数の木が存在することになり、これら全体を「森」と呼びます。この場合、森を構成するすべての木についてサイクルの検出を行う必要があります。白・灰・黒の3つのセットによるアプローチこの手法では、DFS走査を実行する際に、ノードを3つの異なるセットに割り当てて管理します。3

オイラー路（Euler Path）とは、グラフ上のすべての辺をちょうど1回ずつ通過する経路のことです。このとき、同じ頂点を何度訪れても構いません。オイラー回路（Euler Circuit）はオイラー路の特殊な形態で、経路の始点と終点が同じ頂点でつながっている、すなわち「同じ頂点から出発して同じ頂点へ戻る閉じた経路」を指します。この概念は、18世紀の「ケーニヒスベルクの橋の問題」をきっかけにレオンハルト・オイラーが考察したもので、グラフ理論の原点ともいえる考え方であり、「一筆書き」が可能かどうかの判定にも応用されます。 オイラー回路の成立条件 有向グラフがオイラー回路を持つかどうかを判定するに

オイラー路とオイラー回路の概要オイラー路（Euler Path）とは、グラフ内のすべての辺をちょうど1回ずつ通過できる経路のことです。このとき、頂点は何度通っても構いません。一方、オイラー回路（Euler Circuit）は、オイラー路の特別なケースです。オイラー路の始点となる頂点が、同時にその経路の終点とも接続されている場合、つまり「スタート地点に戻ってくる」ような経路が存在するとき、それをオイラー回路と呼びます。オイラー路・オイラー回路の判定条件グラフがオイラー路またはオイラー回路を持つかどうかを判定するには、以下の条件に従います。グラフは連結である必要があります。次数が奇数である頂点がち

フルーリーのアルゴリズム（Fleurys Algorithm）とはフルーリーのアルゴリズムは、与えられたグラフからオイラー路（Euler Path）またはオイラー閉路（Euler Circuit）を求めるための古典的なアルゴリズムです。基本的な考え方はシンプルで、ある辺から出発し、隣接する頂点へ移動するたびに通過済みの辺を削除していきます。この操作を繰り返すことで、ステップごとにグラフが単純化され、最終的にオイラー路やオイラー閉路を効率よく発見できる仕組みになっています。アルゴリズムを適用するための条件オイラー路やオイラー閉路を正しく求めるためには、以下のルールを満たしている必要があります。対

グラフ彩色問題とは グラフ彩色（グラフ・カラーリング）問題は、グラフ理論におけるグラフラベリング（ラベル付け）の特殊なケースです。この問題では、グラフの各頂点（ノード）に対していずれかの色を割り当てていきます。ただし、彩色には重要な制約があり、隣接する2つの頂点に同じ色を割り当てることはできません。 この問題を解くには、一般的に貪欲法（グリーディアルゴリズム）が用いられます。ただし、貪欲法はその時点で最も有利な選択を繰り返す手法であるため、必ずしも最小色数での彩色が保証されるわけではない点に注意が必要です。 入力と出力 入力としてグラフの隣接行列を受け取り、出力として各ノードに割り当てられ

重み付き有向非巡回グラフ(DAG)と、始点となる頂点が1つ与えられます。ここでの目的は、開始ノードからグラフ上の他のすべての頂点までの最長距離を求めることです。この問題はトポロジカルソートを利用することで効率的に解くことができます。まずグラフのノードをトポロジカルソートで並べ替え、その結果をスタックに格納します。その後、スタックから頂点を取り出すたびに、各頂点への最長距離を順次更新していきます。DAGには閉路(サイクル)が存在しないため、負の重みを持つ辺が含まれていても、パスの距離が無限に増大することはありません。そのため、ダイクストラ法やベルマン・フォード法を用いなくても、トポロジカルソート

グラフの頂点集合を、互いに独立した2つの集合に分割でき、グラフ内のすべての辺が「一方の集合から出発して他方の集合で終わる」関係になっている（＝同じ集合の中に辺が存在しない）とき、そのグラフは2部グラフ（バイパータイトグラフ）であるといいます。 2部グラフかどうかの判定は、頂点彩色を用いて行うことができます。同じ集合に属する頂点には同じ色を割り当て、別の集合に属する頂点には別の色を割り当てます。隣接する頂点同士が必ず異なる色になるように塗分けできれば、そのグラフは2部グラフであると判断できます。 入力と出力 入力： 隣接行列 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1

重み付き有向非巡回グラフ(DAG:Directed Acyclic Graph)と、始点となる頂点が与えられます。ここでの課題は、始点ノードからグラフ内の他のすべての頂点への最短距離を求めることです。 最短距離を求めるアルゴリズムとしては、負の重みを含むグラフに対してはベルマン・フォード法、正の重みのみのグラフに対してはダイクストラ法が広く知られています。しかし、対象が有向非巡回グラフ(DAG)である場合は、トポロジカルソート(位相整列)のテクニックを活用することで、これらの汎用アルゴリズムよりも低い計算量で最短経路を求めることができます。 入力と出力 入力:グラフのコスト行列 0 5