Я пытаюсь написать программу, которая использует анализ электрической сетки. Итак, у меня есть узлы схемы [A, B, C, D] и ветви, которые связывают узлы [0,1,2,3,4,5,6,7,8].

Как я могу найти кратчайший цикл в неориентированном графе с несколькими ребрами, как в примере ниже?

Изображение графика (4 узла, 9 ребер / ветвей):

Циклы:

 0-1-0
5-6-5
6-8-6
1-4-2-1
2-7-3-2
4-7-5-4
  

Количество циклов, которые мне нужны, составляет:
Циклы = ветви — (узлы — 1), в этом случае мне нужно 6 циклов.

У меня эти данные хранятся в массивах, подобных этому:

 realNodes = [A,B,C,D];

groupBranches = [[0,1,4,5,6,8], [3,5,6,7,8], [0,1,2,3], [2,4,7]];

// groupArray[0] stores the branch numbers connected to A;
// groupArray[1] stores the branch numbers connected to B;
// groupArray[2] stores the branch numbers connected to C;
// groupArray[3] stores the branch numbers connected to D;

  

Примечания:

Мне не нужны все возможные циклы, мне просто нужно использовать каждое отдельное ребро (ветвь) в некотором цикле.

Также конечные циклы могут отличаться от представленных в примере.

Я был бы рад увидеть алгоритм на любом языке.

Вы можете создать связующее дерево, используя любой алгоритм, который вам нравится (BFS работает).

Затем для каждого ребра, которого нет в дереве, вы создаете цикл, содержащий это ребро плюс путь по дереву от одного конца до другого.