循环枚举具有多边的无向图

问题描述 投票:1回答:1

我正在尝试编写一个使用Electrical Mesh Analysis的程序。所以我有电路[A,B,C,D]的节点和链接节点[0,1,2,3,5,5,7,8]的分支。

如何找到具有多边的无向图中的最短周期,如下图所示?

图形图像(4个节点,9个边/分支):

graph

周期:

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;

Notes:

我不需要所有可能的循环,我只需要在某个循环中使用每个单独的边(分支)。

而且,最终循环可以与示例中呈现的不同。

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

javascript algorithm math graph cycle
1个回答
0
投票

您可以使用任何您喜欢的算法制作生成树(BFS可以工作)。

然后,对于不在树中的每个边,您创建一个包含该边的循环以及从一端到另一端的树中的路径。

© www.soinside.com 2019 - 2024. All rights reserved.