GCJ の問題を解いていると、やっぱりグラフが苦手ということを感じるので『アルゴリズムC』のグラフアルゴリズムの部分を眺めたりしました。それで思ったことはいくつかあるのですが、アルゴリズムがどのようなコードで実現されるのかが見えていないという点…

真ん中あたりから読み始めて 23 章まで。Euler path/circuit の話が出てきて、それが存在するための必要十分条件とその証明。この部分は数学的帰納法の解説にページ数を割いてたりするので流し読み。次に、Euler circuit が存在しない場合に、複数回通る辺が…

一周目終わり。16章以降の内容は全域木、オイラー閉路、マッチング、ハミルトン閉路、巡回セールスマン問題、近似解と下限の評価など。終盤の話は初めて見る内容も多く、詳細はフォローできてないと思います。一周目なので、基本的なものの見方が掴めればい…

ページ数でいうともうすぐ折り返し。ここまでで、最短経路を求める Dijkstra のアルゴリズム、最小全域木を求める Prim, Kruskal のアルゴリズムと、聞き覚えのあるものが三つ出てきました。あとは枝刈りや近似解の話。それからマトロイドの定義が出てきまし…