使用深度优先搜索在Python中实现欧拉回路

Question

我正在尝试编写一个程序，检查给定的矩阵是否有欧拉回路，我正在使用DFS进行检查，但是我的递归调用中存在一些问题。

对于DFSvisited的第一次调用如下所示：DFSvisited(G <- ，0, 1, temp_path = 0)。

def DFSvisited(G,i,j,temp_path):
    G[i][j]=0
    G[j][i]=0
    temp_path.append(j)
    for k in range(0,n):
        if G[j][k]==1:
            print 'j+++',j,"#### k",k
            DFSvisited(G,j,k,temp_path)

我传递一个看起来像这样的矩阵：

   0   1   0   0   0   1   0
   1   0   1   0   0   1   1
   0   1   0   1   1   0   1
   0   0   1   0   1   0   0
   0   0   1   1   0   1   1
   1   1   0   0   1   0   1
   0   1   1   0   1   1   0

但是它返回的temp_path是[0, 1, 2, 3, 4, 5, 6, 6, 4, 6, 5, 6]，而不是第一次迭代中的[0,1,2,3,4,2,6,1,5,0]。

我认为在DFSvisited方法内部的递归调用中我可能错过了某些东西，你有什么想法吗？

谢谢！

- tkyass

Answer 1

你的方法存在问题，DFS遍历的顺序不一定等同于欧拉路径。虽然你的DFS遍历最终会遍历所有边，但可能需要回溯而不是沿着一条连续的路径走。因此，你需要根据DFS回溯的距离将节点插入临时路径中，而不是总是将节点附加到临时路径的末尾。

考虑以下示例图：

如果DFS遍历从a -> b -> c -> a开始，它将会在a处卡住。因此，DFS遍历必须回溯到最后一个具有未遍历边的顶点。这将是顶点b。然后，DFS遍历可以继续使用b -> d -> e -> b。之后，找不到未遍历的边，搜索结束。为了构建欧拉路径，我们不能简单地按照访问顺序连接顶点（即abcabdeb）。相反，我们从构造临时路径abca开始。然后，在我们在a处卡住后回溯到b时，我们必须在临时路径中插入从b访问的顶点。但是，我们不是在结尾处插入，而是在b之后插入它们，结果为abdebca，这是一个有效的欧拉回路。

为了修复您的程序，您可以向DFSvisited方法添加一个参数offset。对于对DFSvisited的初始调用，偏移量将设置为0。对于每个递归调用，偏移量设置为offset+1。然后可以通过在给定的offset处插入到临时路径来替换追加到临时路径中的内容：

def DFSvisited(G,i,j,offset,temp_path):
    G[i][j]=0
    G[j][i]=0
    n = len(G)
    temp_path.insert(offset, j)
    for k in range(0,n):
        if G[j][k]==1:
            DFSvisited(G,j,k,offset+1,temp_path)

- f9c69e9781fa194211448473495534