グラフ

頂点（ノード）と辺から成り立っている。
頂点に方向性を持った辺の有無によって、無向グラフと有向グラフに分けられる。
辺にはコストと呼ばれる重さを設定することもある。これらは道の最短路問題とかに使われる。
閉路は頂点と辺をつないでいく中でまた同じノードをたどる経路のことである。
パスは閉路と違って同じノードをたどらない経路である。

グラフの表現

隣接行列
ノードから訪問できるノードに対して2進数形式で表現する。ノード別にすべてのノードに関係を示さなければならないので、ノード数の2乗の計算量になる。
コストが指定される場合、コストを記録して隣接ない部分ついては大きい定数にする。

隣接リスト
行列では隣接ない部分まで表現しないといけないから、リストにするとノードから進行できるところだけ記録するのが、隣接リストである。

ダイクストラ

指定したノードから行けるすべてのノードの最短路を探す。

流れ
１．出発するノードから行けるノードのコストを記録、行けないノードについては大きい定数にする。
２．他のノードを訪問し、そのノードから行けるノードのコストを記録
３．2のコストが1より小さい場合、コストを2に変更
123を全探索できるまで繰り返す。

クラスカル

辺が短い順に追加して、最短路を作る。

流れ
１．辺を昇順に整列させる。
２．辺を追加していく、コストも記録。
３．ループ、閉路になる辺は飛ばす。
４．123を全探索になるまで繰り返す。
コードでは昇順の部分はunion-findを用いている。