python 无向图构建欧拉图

构建欧拉图需要满足以下两个条件：

1. 所有节点的度数都是偶数；
2. 图是联通的。

下面是一个示例代码，实现了无向图构建欧拉图的功能：

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def is_eulerian(self):
        # 判断所有节点的度数是否都是偶数
        for node in self.graph:
            if len(self.graph[node]) % 2 != 0:
                return False

        # 检查图是否联通
        visited = set()
        self.dfs(list(self.graph.keys())[0], visited)

        for node in self.graph:
            if node not in visited or len(visited) != len(self.graph):
                return False

        return True

    def dfs(self, node, visited):
        visited.add(node)
        for neighbor in self.graph[node]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

    def find_eulerian_path(self):
        if not self.is_eulerian():
            return None

        start_node = list(self.graph.keys())[0]
        path = []
        self.eulerian_path(start_node, path)

        return path

    def eulerian_path(self, node, path):
        while self.graph[node]:
            neighbor = self.graph[node].pop()
            self.graph[neighbor].remove(node)
            self.eulerian_path(neighbor, path)
        path.insert(0, node)

g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(3, 6)
g.add_edge(4, 7)
g.add_edge(5, 6)
g.add_edge(6, 7)

path = g.find_eulerian_path()
if path:
    print("欧拉路径为：", path)
else:
    print("该图不是欧拉图")

这个示例代码中，我们使用了深度优先搜索（DFS）来检查图是否联通，使用递归的方式来构建欧拉路径。如果图不满足欧拉图的条件，则返回 None。如果图是欧拉图，则返回欧拉路径。