はじめに

• 基本的なグラフアルゴリズムをＣ言語で実装したサンプルプログラムと、その実行例をアップしています。
• グラフは隣接行列で表現しています。
• 文字コードは Shift-JIS コードを使っています。
• gcc をお使いのときは文字コードを指定するオプションを付けてください：
  
  gcc --input-charset=cp932 hoge.c

  EUC 版はこちら / UTF-8 版はこちら

  ブラウザ画面からコピー＆ペーストすると文字コードの関係で正しく動作しないことがあります。 使用するときは「リンク先を保存」などで保存してください。

  プログラムは更新することがありますので、動作がおかしいときは最新版を 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-次元立方体グラフ /
  ランダムなグラフ（頂点数12） / ランダムなグラフ（頂点数64）

有向オイラーグラフ

• オイラーサーキットを求めるプログラム : 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