ここ に置いておきます.
実験用の部分が多いです.
蟻本と Spaghetti Source にかなり影響をうけています.
割とどうしてくれても良いですが, WAやTLE喰らっても知りません.
理解してから, (他の人のソース見ながらでも)自分で実装する事をおすすめします.
どういうデータが欲しいかに従って, 自分で計測して下さい.
参考として, 自分の環境で, 自分が書いたコードが 秒程度かかるものを挙げます.
但し, グラフの構築にかかる時間は無視しています.
特にランダムは, ケース数少ないし, 信用できるようなデータではないと考えた方がよいです.
| ケース | 頂点数 | 辺数 |
|---|---|---|
| ランダムを80ケース(合計) | 5000 | 1000000 |
| ランダムを40ケース(合計) | 50000 | 1000000 |
| ランダムを13ケース(合計) | 500000 | 1000000 |
| 密なランダムを5ケース(合計) | 5000 | 約 |
| 完全グラフを15ケース(合計) | 2000 | |
| ワーストケース1つ目 | 7000 | 13997 |
| ワーストケース2つ目 | 628 | 33491 |
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか？最初に g に来たときに c に戻るのはなぜでしょうか．
私が理解していない/勘違いしていたら済みません．