fleury算法 python

Fleury算法是一种用于寻找欧拉回路的算法。以下是Python实现：

def fleury(graph):
    # 检查图是否连通，如果不是则返回None
    if not is_connected(graph):
        return None
    
    # 复制图以防止修改原始图
    graph = copy.deepcopy(graph)
    
    # 初始化起始点
    start_vertex = list(graph.keys())[0]
    curr_vertex = start_vertex
    
    # 初始化欧拉回路
    euler_circuit = [start_vertex]
    
    while graph:
        # 如果当前点有未访问的边，则继续沿着该边走
        if any(graph[curr_vertex]):
            for i, v in enumerate(graph[curr_vertex]):
                if v:
                    # 记录下一步要走的点
                    next_vertex = i
                    
                    # 删除该边
                    graph[curr_vertex][i] = graph[i][curr_vertex] = 0
                    
                    # 如果下一步要走的点是一个桥，则检查是否有其他桥，如果没有则先走该桥
                    if is_bridge(graph, curr_vertex, next_vertex):
                        if not has_other_bridge(graph, curr_vertex, next_vertex):
                            euler_circuit.append(next_vertex)
                            curr_vertex = next_vertex
                            break
                        else:
                            graph[curr_vertex][i] = graph[i][curr_vertex] = 1
                    else:
                        euler_circuit.append(next_vertex)
                        curr_vertex = next_vertex
                        break
        # 如果当前点没有未访问的边，则回溯到上一个点
        else:
            for i, v in enumerate(euler_circuit[::-1]):
                if any(graph[v]):
                    curr_vertex = v
                    euler_circuit = euler_circuit[:-i-1] + euler_circuit[-i-1:]
                    break
                    
    return euler_circuit

其中，`is_connected`函数用于检查图是否连通，`is_bridge`函数用于检查一条边是否是桥，`has_other_bridge`函数用于检查删除一条桥边后是否还有其他桥。