オイラー閉路を探すアルゴリズム

1年前に書いたオイラー閉路を探すプログラムを見たら%$O(|E|^2)$%だったので,書き直しました.


オイラー閉路とは?


一言で説明すると,始点と終点が一致した一筆書き.


ソースコードはこちら:
https://gist.github.com/buyoh/c585cca480dbcaad5e17e2cbeb89fdae
わかりにくかったらごめんね.



オイラー閉路の存在判定


あるグラフがあって,そのグラフ上でオイラー閉路が構築可能か?という問題.
グラフ理論の起源と深く関連する.

グラフが連結であって,かつ全ての頂点の次数が偶数ならば構築可能である.



オイラー閉路の構築


オイラー閉路の存在が分かっているグラフがあって,実際にどのようなオイラー閉路が描けるのか求める問題.


オイラー閉路の構築アルゴリズム@深さ優先探索


愚直に深さ優先探索を使って求めると,バックトラックが頻繁に発生するケースが考えられるため,
最悪時間計算量は多項式時間で収まらない.


オイラー閉路の構築アルゴリズム@連結性のチェック


そこで,『この辺を削除したときに連結性が失われるか』を判定しながら辺を選んでいく方法を考える.
連結性の判定には%$O(|E|)$%掛かるため,全体の時間計算量は%$O(|E|^2)$%である.


オイラー閉路の構築アルゴリズム@複数の閉路検出+結合


全ての頂点の次数が偶数,という点に注目する.

『オイラー閉路の存在が分かっているグラフ』は複数の閉路に分割することが出来る.証明略.

なので,後戻りしない深さ優先探索を行って,グラフから閉路を求めておく.各辺には閉路番号を割り当てておく.

閉路集合を求めた後,適当な辺から開始して,グラフを辿っていく.
別の閉路と合流したら,その閉路に飛び移る必要がある.ただし,あてずっぽうに飛び移ると,行き詰まることがある.

次のような戦略を考えて,行き詰まらないようにする.
・載ったことがない閉路には積極的に飛び移る.
・どの分岐も載ったことがある閉路ならば,直近で載った閉路の分岐を選ぶ.

多分これで求めることが出来る.
全体の時間計算量は%$O(|E|)$%

ちゃんとverifyした訳ではないので,来週にはこの記事が消えているかもしれない.



オイラー路の構築


オイラー路とは,閉路じゃない一筆書きのこと.
オイラー閉路の構築アルゴリズムを使って,オイラー路を構築することが出来る.

まず,頂点次数が奇数であるような頂点が2つ存在するはずなので,その頂点を見つける.
その2つの頂点の間に辺を加える.
そして,そのグラフ上で加えた辺を始点とするようなオイラー閉路を求める.
最後に,加えた辺を取り除く.オイラー路完成.


スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1373位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
237位
アクセスランキングを見る>>