algorithm - 获取图中的所有网格(窗口)

Question

我必须在表示电路的未加权图中获取所有网格的列表(窗口/循环/基本电路，一起覆盖图形所有边缘并且没有人包含其他循环的最短循环)用于该电路的网格分析(我可以假设它是一个平面图)。从文件加载图形(表示为元组 (A,B,R)，表示两个顶点和边的电阻)。

我将 Python 与 NetworkX 库一起使用，但它的 cycle_basis 函数不返回网格(它们显然与循环基础不同)。该图是无向的，所以我不能使用 simple_cycles 函数。我尝试为此任务修改 BFS，但我无法保证其他循环中不包含任何循环。

我可能需要这样的东西:Algorithm for finding minimal cycles in a graph ，但是这个问题在上一条评论中没有任何算法证明，我希望我的问题的答案比“实现霍顿算法”更简单。

Answer 1

网格分析需要的是图形的任何特定平面图中的封闭区域列表。

它比最小循环基础更容易找到，但你得到哪个列表取决于你使用的平面图。

如果您有平面图，并且可以按顺时针或逆时针顺序获取每个顶点的邻居，那么只需在这些封闭区域周围进行追踪就非常容易。

否则，你可以这样做:

1. 生成生成树
2. 对于树中不的每条边，制作一个仅包含该边的循环，加上生成树中的边。

由于每个循环都包含一个不在任何其他循环中的边，因此可以保证没有循环包含在任何其他循环中......取决于你所说的“包含”是什么意思。重要的一点是，只要您注意任何电流源，这些循环就可以用于分析。也许您想在生成树中避免使用它们。

由于您将使用这些循环来生成要求解的方程组，其中每条边都是一个变量，因此使用更复杂的算法来查找“更小”的循环可能没有任何优势。