私はグラフの問題に取り組んでおり、一意のパスを見つけることを理解しようとしています
例を挙げましょう。次のように、4 つのノードとエッジを持つ 6 つのエッジを持つグラフを考えてみましょう。
1 2
2 3
3 4
4 1
1 3
2 4
長さ 5 の一意の巡回パスは次のようになります -
1 -> 2 -> 3 -> 4 -> 1
1 -> 3 -> 2 -> 4 -> 1
1 -> 2 -> 4 -> 3 -> 1
パスのエッジのセットが等しい場合、2 つのパスは等しいと見なされます。2 つのパス 1 -> 2 -> 3 -> 4 -> 1 および 1 -> 3 -> 2 -> 4 -> 1 を考慮してください。最初のパスはセット = [(1,2), (2,3) です。 ), (3,4), (4,1)]、2 番目は = [(1,3), (3,2), (2,4), (4,1)]
明らかに、2 つのセットが異なるため、パスも異なります。2 つのセット (パス) 間の共通のエッジの存在を比較しているだけなので、エッジの順序は関係ありません。
循環パスを取得したら、パスに同じノード セットがあるかどうかを確認するにはどうすればよいですか? すなわち、1 -> 2 -> 3 -> 4 -> 1 と 1 -> 4 -> 3 -> 2 -> 1 は同じ集合、すなわち
[(1,2), (2,3), (3 ,4), (4,1)] 別の順序で。
セットのペアのマップを実装し、重複をチェックすることを考えました..まだより良いオプションを探しています。続行する方法について何か助けをいただければ幸いです。