Уникальный неориентированный циклический граф путей

Я работаю над проблемой в графах и пытаюсь разобраться в поиске уникальных путей

приведу пример, рассмотрим граф с 4 узлами и 6 ребрами с ребрами следующим образом —

1 2


2 3


3 4


4 1


1 3


2 4

уникальные циклические пути длиной 5 будут —

  1. 1 -> 2 -> 3 -> 4 -> 1
  2. 1 -> 3 -> 2 -> 4 -> 1
  3. 1 -> 2 -> 4 -> 3 -> 1

    Два пути считаются равными, если множество ребер пути равно. рассмотрим два пути 1 -> 2 -> 3 -> 4 -> 1 и 1 -> 3 -> 2 -> 4 -> 1 Первый путь-это просто набор = [(1,2), (2,3), (3,4), (4,1)], а второй = [(1,3), (3,2), (2,4), (4,1)]
    Ясно, что эти два набора различны, и, следовательно, таковы пути. Порядок ребер не имеет значения, так как вы сравниваете только наличие общих ребер между любыми двумя наборами (путями).

После того, как я получу циклические пути, как я проверю, имеют ли пути тот же набор узлов в пути? я.Е , 1 -> 2 -> 3 -> 4 -> 1 и 1 -> 4 -> 3 -> 2 -> 1 имеют те же наборы, я.е

[(1,2), (2,3), (3,4), (4,1)] в ином порядке.

Я подумал о реализации Карты парных наборов и проверке дубликатов.. все еще ищу лучшие варианты.
Любая помощь ценится о том, как продолжить?

1 ответ