グラフ・プログラム Python 版

2011.6.14, 描画もできるように Graph と言うクラスを定義する形に改めました。

関数定義ファイル

深さ優先探索(DFS)

幅優先探索(BFS)

  • 隣接行列による実装例 BFS.py
  • 隣接リストによる実装例 BFSAL.py

連結成分への分解

最小連結子

最短路問題

オイラーグラフ

郵便配達員問題

  • 実装例 Postman1.py(組合せを全て求める方法)
    ... 最大マッチングアルゴリズムを応用する方法は後日

彩色数・彩色多項式

最大フロー

二部グラフの最大マッチング

重み付き二部グラフの最大マッチング

グラフ描画ツール Python 版(学内限定)

戻る