質問: グラフ中に含まれる長さが3と4の閉路を求めるアルゴリズムを考えています。 なにか良いアイデアはないでしょうか? (グラフの情報は外部からストリームして、C言語で開発しています。) ただし、以下のような場合は長さ3の閉路が2つで4の閉路があるとはカウントしません。 ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/8f357125e464257356c818ced3466240.jpeg)
回答: アイデアということなので。 長さが3の閉路は、スタートのノードと結ばれる2つのノードを必ず含みます。(質問の図でいうと、スタートをiとすると、[v1,v2],[v1,j],[v2,j]のいずれかが候補になる)また、この候補の組み合わせのノード間には必ずエッジがあります。(長さ3のうち、2つのノードで長さ2が消費されるため) よって、上記の条件を実装すれば長さ3の閉路の検出ができることになります。もう少し具体的にいうと 1.ノード間のエッジの有無を0と1で表現した行列(Xとする)を準備する。(縦軸をi,v1,v2,j、横軸をi,v1,v2,jとして交差する部分にエッジがあれば1、なければ0を設定) 2.Xの行数分、以下の処理を実施 1)特定の行を取り出して1が設定されているインデックスを検出(x[0,:]であれば、[0,1,1,1] なので、[1,2,3]となる。 2)上記の[1,2,3]から2つを取り出した組み合わせを生成([1,2],[1,3],[2,3]となる) 3)Xから上記の組み合わせの要素を取り出して1であれば長さ3の閉路と判定 3.重複ケースをチェックして除外 というコードでうまくいくはずです。 長さ4の閉路もおおよそは上記のルールの応用でうまくいくはずです。スタートのノードと結ばれるノード2つが候補というところまでは同じです。長さ4の場合は、この候補各々と結ばれるノードを検出してこのノードの集合の積を取った結果、残ったノードがあれば長さ4のノードということになります。 上記もエッジの有無を表す行列を使えば、それほど難しくないはずです。 最後の「以下のような場合は長さ3の閉路が2つで4の閉路があるとはカウントしません。」については以前に回答した記憶があるので確認願います。 細かなケースは検証していないので、実装して問題の有無を確認願います。