javascript - 多边无向图的循环枚举

Question

我正在尝试编写一个使用 Electrical Mesh Analasys 的程序。所以我有电路 [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

我需要的周期数是：Cycles = Branches - (Nodes - 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;

笔记：

我不需要所有可能的循环，我只需要在某个循环中使用每一个边缘（分支）。

此外，最终循环可能与示例中的不同。

我很高兴看到任何语言的算法。

标签： javascriptalgorithmmathgraphcycle

Answer 1

您可以使用您喜欢的任何算法制作生成树（BFS 有效）。

然后，对于不在树中的每条边，您制作一个包含该边的循环以及从一端到另一端穿过树的路径。