組合せとグラフの理論（塩田）　2006年度教材 プログラム編

はじめに 基本的なグラフアルゴリズムをＣ言語で実装したサンプルプログラムと、その実行例をアップしています。 グラフは隣接行列で表現しています。 文字コードは EUC コードを使っています。 プログラムは更新することがありますので、動作がおかしいときは最新版を download してください。 関数定義部 基本的な関数の定義部 : graph.h 有向グラフ関数定義部（ dijkstra.c, eulerdigraph.c, debruijn.c で引用 ） : digraph.h 迷路アルゴリズム関数定義部（ maze.c で引用 ） : maze.h 多項式関数定義部（ chromatic.c で引用 ） : graphpol.h 彩色多項式・彩色数関数定義部（ chromatic.c で引用 ） : chromatic.h 平面性判定関数定義部（ planarq.c で引用 ） : planar.h オイラーグラフ オイラー性判定と、オイラーサーキットを求めるプログラム : eulergraph.c 実行例 : 完全グラフ / 完全二部グラフ / k-次元立方体グラフ / ランダムなグラフ 有向オイラーグラフ オイラーサーキットを求めるプログラム eulerdigraph.c と 実行例 ドゥブリュエイン列 ドゥブリュエイン列を求めるプログラム : debruijn.c 実行例 : ３シンボルの３文字単語 / ２の６ / ７の３ 探索木 深さ優先探索を用いて u-v 道を求めるプログラム : dfs.c 広さ優先探索を用いて u-v 道を求めるプログラム : wfs.c 深さ優先・広さ優先探索の比較プログラム : dfswfs.c dfswfs.c の実行例 : 頂点数 8 / 頂点数 16 / 頂点数 32 / 頂点数 64 ( 25.0KB ) / 頂点数 128 ( 99.3KB ) 迷路 広さ優先探索を用いて迷路を解くプログラム maze.c と 実行例 最短路問題 Dijkstra のアルゴリズムのプログラム dijkstra.c 実行例 : 頂点数 16 / 頂点数 32 / 頂点数 64 / 頂点数 8 の有向グラフ / 頂点数 16 の有向グラフ 郵便配達員問題 奇数次数の頂点が２個の場合の郵便配達員問題を解くプログラム postman2.c 実行例 : 頂点数 8 / 頂点数 16 最小連結子問題 最小連結子を求めるプログラム minspantree.c 実行例 : 頂点数 8 / 頂点数 16 / 頂点数 32 平面性 平面性を判定し、平面的なときは描画法も提示するプログラム planarq.c 実行例 : 立方体グラフ / 完全二部グラフ K2,5 / 完全二部グラフ K3,3 / 星グラフ / ランダムなグラフ 彩色 彩色多項式と彩色数を求めるプログラム chromatic.c 実行例 : 完全グラフ / 完全二部グラフ / 立方体グラフ / 和グラフ / 閉路 / ピータースングラフ / ランダムな木 / ランダムなグラフ ネットワーク ネットワークの最大フローを求めるプログラム maxflow.c 実行例 : 頂点数 8 / 頂点数 32 連結成分分解 単純無向グラフを連結成分に分解するプログラム decomp.c ブロック分解 単純無向連結グラフをブロック分解するプログラム blockdecomp.c 実行例 : 頂点数 16 / 頂点数 32 戻る