グラフ関係のコードいくつか

ようやく大学が夏季休業に入ったので、学校で使った離散数学の本読んでグラフ理論とオートマトンの勉強をしている。
グラフ理論の部分で出てきたアルゴリズムとかでコード書いたのでいくつか。


Bellman-Ford algorithm
まずはBellman-Ford法。これは本には出てこなかったけど、Dijkstra法は書いたことあるのにBellman-Ford法は書いた事ないなぁと思った程度のアルゴリズム力なので、とりあえず書いてみた。



一応無向グラフ想定して書いたけど、ちょっと変えれば有向グラフにも適用出来る……はず。一応辺は行列で表現してるので。

Kruskal's algorithm
次にKruskal法。最小全域木を求めるアルゴリズムで、O(ElogE)? O(ElogV)? なアルゴリズム。



同じ木に属しているかどうかはUnion-Find木で書けるので、本の通りにいけば、まずは辺をコストでソートして、小さい辺から、その辺が連結でない2つの木を連結するならば、最小全域木の辺として加えていくというアルゴリズム。

Reverse Polish Notation
アルゴリズムではないけども、逆ポーランド記法をプログラミング3年目?にしてようやく実装したので。



ある数式を表す木構造を考えるときに、木の各頂点に番号を付けることを考えると、プリオーダーとポストオーダーという2つの方法が考えられる。
プリオーダーって言うのは、自分自身、左の子ノード、右の子ノードの順に再帰的に番号を付けていく方法で、このやり方だと式木はポーランド記法になる……はず。
ポストオーダーは左の子ノード、右の子ノード、自分自身の順に番号をつけていく方法で、このやり方だと式木は逆ポーランド記法になる。

実装の方法としては、入力をスペース区切りの数字、演算子の列だとして、数字が来たらスタックにそのままプッシュ、演算子が来たら右、左の順にスタックから取り出した値を子ノードとして割り当てて、演算子を根とした木構造にしてスタックにプッシュ。最後にスタックに残った木を取り出すと、これが式木になってる。後はまぁコードの通りに各頂点ごとの値を計算するだけ。

とりあえずグラフは(まだフローとかあるけど)ひと通り分かった……と思うので、次はオートマトンのあたりで何かしらコードを書きたい。