多边无向图的圈枚举

Question

我正在编写一个使用电网格分析的程序。所以我有电路的节点[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;

我很乐意看到任何语言的算法。

Answer 1

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

然后，对于不在树中的每条边，你做一个循环，包含该边加上从树的一端到另一端的路径。