具有多边的无向图的循环枚举 [英] Cycle enumeration of an undirected graph with multi edges

查看:96
本文介绍了具有多边的无向图的循环枚举的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

I'm trying to code a program that uses Electrical Mesh Analasys. So I have the nodes of the circuit [A,B,C,D] and the branches that links the nodes [0,1,2,3,4,5,6,7,8].

如何像示例波纹管那样在具有多个边的无向图中找到最短的周期?

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

Graph image (4 nodes, 9 edges/branches):

周期:

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

我需要的周期数是: 周期=分支-(节点-1),在这种情况下,我需要6个周期.

The number of cycles that I need are: Cycles = Branches - (Nodes - 1), in this case I need 6 cycles.

我将这些数据存储在这样的数组中:

I have this data stored in arrays like this:

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:

I don't need all the possible cycles, I just need to use every single edge (branch) in some cycle.

此外,最终循环可能与示例中显示的有所不同.

Also, the final cycles can vary from the presented in the example.

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

I would be happy to see an algorithm in any language.

推荐答案

您可以使用任意喜欢的算法制作生成树(BFS可以使用).

You can make a spanning tree using any algorithm you like (BFS works).

然后,对于不在树中的每个边缘,进行一个循环,其中包含该边缘以及从一端到另一端的穿过树的路径.

Then, for every edge that's not in the tree, you make a cycle containing that edge plus the path through the tree from one end to the other.

这篇关于具有多边的无向图的循环枚举的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆