如何从这样的图中删除所有循环？所有边长均为一，并且所有边都是垂直或水平的。该图已连接。
我想计算为了使图形不包含循环而必须删除的边的最小数量。
如果您包含示例代码(最好是 C++、C 或 Java)，那将会非常有帮助。
更新:显然我必须找到顶点和边的数量。 我遇到的问题给出了一组指令，例如(下，左，上，下，左，左，上，下)。从坐标平面中的 (0, 0) 开始，沿指定方向移动一个单位。这将创建一个图表。我如何从这组指令中获取顶点和边的数量？
最佳答案
由于图形是连通的，如果该点如您所写，为
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非常简单。
关于c++ - 通过查找顶点和边从连通图中删除循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34823742/