为什么我寻找图的欧拉回路的代码只部分有效？

Question

我创建了一个叫做“电路”的函数，它可以在图中遍历，直到回到起点。现在我想让它一直运行，只要还有空闲的顶点，就能找到所有的路径。目前我只是想把新路径添加到已有路径中，但我知道必须在正确的位置插入，才能得到一个有效的欧拉回路。不幸的是，经过长时间的反复尝试，我还是没能让第二部分正常工作。

我希望能得到一些帮助。谢谢！

这是我的代码：

verts = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 3), (6, 3), (2, 5), (5, 4), (3, 4), (6,2)]


# find circles
def circuit(current, path = []):
    path.append(current)
    
    if current in verts:
        verts.remove(current)
    elif current[::-1] in verts:
        verts.remove(current[::-1])
    
    
    if path[0][0] == current[1]:
        return path
    
    for i in verts:
        if current[1] == i[0]:
            return circuit(i, path)
        elif current[1] == i[1]:
            return circuit((i[1], i[0]), path)
        
    
# loss = random.randint(0,10)
# print(circuit(verts[loss]))

start = (1, 2)
path = []
if path == []:
    path += circuit(start)

while len(list(verts)) > 0:
    for unusedVert in list(verts):
        
        for pathVerts in path:
            if unusedVert[0] == pathVerts[0]:
                print(1)
                path.append(circuit(unusedVert))
                break
            elif unusedVert[0] == pathVerts[1]:
                print(2)
                path.append(circuit((unusedVert[1], unusedVert[0])))
                break
            elif unusedVert[1] == pathVerts[0]:
                print(3)
                path.append(circuit(unusedVert))
                break
            elif unusedVert[1] == pathVerts[1]:
                print(4)
                path.append(circuit((unusedVert[1], unusedVert[0])))
                break

                    
print(path)

Answer 1

这里有几个问题：

• 默认参数设置 path = [] 是危险的，因为在Python中，这个默认值只会创建一次，这会对你的代码产生不好的影响。想了解更多，可以查看这个链接："最小惊讶原则"和可变默认参数。

• path.append(circuit(unusedVert)) 这个写法是不对的，因为它只会向 path 添加 一个 项，而 circuit 返回的是一个列表，所以这个元素会变成一个 列表（嵌套在 path 里面）。

• 如果你想要 扩展 路径，你可能无法按正确的顺序收集电路的边，因为在四个 if 条件中的一个匹配可能出现在路径的中间，这样下一个边就应该 插入到那个位置。

我建议使用一个支持旋转的双端队列（deque），这样可以方便你进行需要的插入操作（最后一点）。另外，我建议先创建一个邻接表，这样可以避免多次遍历边的列表。

下面是一个可能的实现方式：

from collections import defaultdict, deque

def create_graph(edges):
    adj = defaultdict(set)
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    return adj

def has_circuit(adj):
    return all(len(neighbors) % 2 == 0 for neighbors in adj.values())

def get_circuit(edges):
    adj = create_graph(edges)
    if not has_circuit(adj):
        ValueError("Graph has no Euler circuit")

    node = edges[0][0] # Any starting vertex
    circuit = deque()
    for _ in range(len(edges)):  # Each iteration removes an edge
        if not adj[node]: # There is no more unused edge here
            # A circuit completed, but not including all edges
            # Find insertion point to extend current circuit
            while not adj[circuit[0]]:
                circuit.rotate()
            node = circuit[0]
        circuit.append(node)
        # Choose next edge
        neighbor = adj[node].pop()  # remove it in one direction
        adj[neighbor].remove(node)  # ...and in the other direction
        node = neighbor  # Traverse it
    return list(circuit)

调用方式如下：

verts = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 3), (6, 3), (2, 5), (5, 4), (3, 4), (6,2)]

circuit = get_circuit(verts)

结果将是一个 顶点 的列表（而不是边），因为这意味着边是什么——列表中的最后一个顶点被理解为连接回第一个顶点：

[6, 1, 2, 3, 4, 5, 2, 6, 3, 5]