今回はクラスカル法(Kruskal法)のプログラムに挑戦したのだが、Prim法に比べてプログラム作成には苦戦した。Kruskal法はPrim法と同じく最小全域木(MST)を求めるためのアルゴリズムで、Prim法と異なり、グラフが連結でない場合にも利用出来る。しかし、今回の…

特にテーマもなくBlogを初めたので、しばらくはグラフ理論のアルゴリズムに関するプログラムをF#を使って書いていくことにしてみようと思う。今回はPrim法で、入力データは前回と同じもの。グラフが与えられた時に、全ての点を通り、コストの総和が最小にな…

最短経路繋がりで、ワーシャルフロイド法を用いて全ての2点間の最短距離を求めてみた。入力データは前回用いたものと同じ(隣接行列表現)なので、結果の二次元配列の最初の要素はダイクストラ法で求めたものと同じ出力結果になっている。 #light "off" //ワー…

グラフ理論の勉強用にグラフの元データからグラフを可視化するプログラムを作成してみた。Graphクラスのコンストラクタにノード数と(点A、点B、AB間のコスト)の配列を渡せばグラフが表示される。見栄えは、微妙。アルゴリズムは非常に単純で、グラフのノード…

練習がてら、F#でダイクストラ法のアルゴリズムを実装してみた。といっても最短距離を求めるところまでで、最短経路は求めていない。入力データはこのページにあるものをそのまま利用させてもらった。このページはわかりやすくてためになります。プログラム…

Wikipediaで見て知っていたので、Hub FSでこんなタイトルの記事を見つけてにやけてしまった。 元ネタHub FSのスレッド中身は、バージョンアップでbaseがキーワードになったため、言語仕様のページのサンプルが動作しなくなっている、という内容でした。

自分用メモ。 f#自体には対応していないが、ocamlに対応しているので次のようにすればOK >|ocaml| ソースコード