#javascript #algorithm #math #graph #cycle
#javascript #алгоритм #математика #График #цикл
Вопрос:
Я пытаюсь написать программу, которая использует анализ электрической сетки. Итак, у меня есть узлы схемы [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;
Примечания:
Мне не нужны все возможные циклы, мне просто нужно использовать каждое отдельное ребро (ветвь) в некотором цикле.
Также конечные циклы могут отличаться от представленных в примере.
Я был бы рад увидеть алгоритм на любом языке.
Ответ №1:
Вы можете создать связующее дерево, используя любой алгоритм, который вам нравится (BFS работает).
Затем для каждого ребра, которого нет в дереве, вы создаете цикл, содержащий это ребро плюс путь по дереву от одного конца до другого.