为什么我用于查找图的欧拉电路的代码只能部分工作？

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))

  不正确，因为这只将 one 条目添加到

  path

  ，并且因为

  circuit

  返回一个列表，所以该元素将是 list（嵌套在

  path

  内）

• 如果打算扩展路径，您将不会以正确的顺序收集电路边缘，因为四个

  if

  条件之一的匹配可能位于路径中间的某个位置，因此应插入下一条边缘在路径中的那个点。

我建议使用支持旋转的双端队列，这有助于您需要执行的插入（最后一个要点）。另外，我会首先创建一个邻接列表，以避免对边列表进行多次迭代。

它的工作原理如下：

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]