c++ - 通过查找顶点和边从连接图中删除循环

Question

如何从这样的图中删除所有循环？所有的边长都是一，所有的边要么是垂直的，要么是水平的。该图已连接。

我想计算为使图形不包含循环而必须删除的最小边数。

如果包含示例代码(最好是 C++、C 或 Java)，那将非常有帮助。

更新:显然我必须找到顶点和边的数量。我遇到的问题给出了一组指令，如(下、左、上、下、左、左、上、下)。您从坐标平面中的 (0, 0) 开始，沿指定方向移动一个单位。这将创建一个图表。我如何从这组指令中获取顶点和边的数量？

Answer 1

因为图是连通的，如果你写的点是

compute the smallest number of edges that need to be removed in order for the graph to contain no cycles

那么你真的不需要写算法。众所周知，去除环的结果是一棵树，所有树的边数相同(顶点数减一)。

---

如果重点是实际枚举剩余的边(或移除的边)，那么您可以使用 DFS(深度优先搜索)。具体来说，在 output of DFS ，您只需要保留那里标记为“树边”的部分。

虽然有用于 DFS 的 C++ 库，但它们可能不会以这种方式枚举边，您自己编写代码可能更容易。如您所见，pseudocode非常简单。