メッシュ構造において、よいサイクル検出方法がうかびません‥

質問

メッシュから適当に複数辺を選択したとき、サイクルを形成するか調べるプログラムを書こうとしています。具体的には以下です。

メッシュ構造は、4×4や5×5程度を想定しています。
（↓........は無視して見てください。見にくくてすみません）
0---1---2---3
|.........|.........|.........|
4---5---6---7
|.........|.........|.........|
8---9---10--11
|.........|.........|.........|
12--13--14--15

現状では、上記のように点に番号をふり、
辺は(5,9)や(10,14)などで表しています。
（辺に番号を振ることも考えてはいます）

辺が24個ありますが、たとえば
ここから適当に12個の辺を選んだ時に、
それらがサイクル（0-1-5-4-0 や 1-2-3-7-6-5-1 など）を
形成しているか、していないか、判別するプログラムを書こうとしています。
が、うまい判別方法が思い浮かびません…。
あらかじめ、4×4、5×5ごとに全てのサイクルを求めておいて、
サイクル1つ1つについて、選んだ辺⊇サイクルの辺？
を確認するしかないでしょうか？
サイクル数が多そうなので、サイクルを求めるのもサイクルを含むかの確認も時間かかりそうで、やりたくないのですが…。（特に5×5では…）

何かもっと簡単な方法orよさそうな方法ありますでしょうか？
ご意見を、伺いたいです。よろしくおねがいします。

回答No.3

επιστημη（@episteme） · ベストアンサー

一本の辺が伸びている頂点Pを探し、その辺を取り除く。
この作業を繰り返し、辺がなくなればサイクルなし。

お礼

ありがとうございます!

回答No.4

rabbit_cat

単純に深さ優先探索でもして、
一回行ったことがある頂点にもう一回到達したらサイクル、でいいんでは。

お礼

それでもいいですね、ありがとうございますー

回答No.2

ICE_FALCON

#1です。
> ここから適当に12個の辺を選んだ時に
すみません。読み飛ばしてました。
余った辺の処理考えて無かったです。
#1のやりかただけでは駄目ですね・・・。

回答No.1

ICE_FALCON

例えば、
１回目　0-1
２回目　1-5
３回目　5-4
４回目　4-0
を選択。
点0,1,4,5を「２回」ずつ呼び出してますね。
「２回」ずつ呼び出している->サイクルができてます。