Python Euler回路/路径检测代码修复：测试用例输出异常

我看了你的代码和测试用例，问题主要出在节点编号处理逻辑和连通性检查的错误判断上，导致正确的环结构没有被识别为欧拉回路。下面是修复后的完整代码，以及详细的问题分析：

修复后的代码 #

# Python program to check if a given graph is Eulerian or not
# Complexity : O(V+E)
from collections import defaultdict

# This class represents an undirected graph using adjacency list representation
class Graph:
    def __init__(self):
        self.graph = defaultdict(list) # default dictionary to store graph

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    # A function used by isConnected
    def DFSUtil(self, v, visited):
        # Mark the current node as visited
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if not visited.get(i, False):
                self.DFSUtil(i, visited)

    '''Method to check if all non-zero degree vertices are connected.
    It mainly does DFS traversal starting from node with non-zero degree'''
    def isConnected(self):
        # If there are no edges in the graph, return true
        if not self.graph:
            return True

        # Mark all the vertices as not visited (using dict to handle arbitrary node IDs)
        visited = {node: False for node in self.graph.keys()}

        # Find a vertex with non-zero degree
        start_node = None
        for node in self.graph.keys():
            if len(self.graph[node]) > 0:
                start_node = node
                break

        # Start DFS traversal from a vertex with non-zero degree
        self.DFSUtil(start_node, visited)

        # Check if all non-zero degree vertices are visited
        for node in self.graph.keys():
            if not visited[node] and len(self.graph[node]) > 0:
                return False

        return True

    '''The function returns one of the following values
    0 --> If graph is not Eulerian
    1 --> If graph has an Euler path (Semi-Eulerian)
    2 --> If graph has an Euler Circuit (Eulerian) '''
    def isEulerian(self):
        # Check if all non-zero degree vertices are connected
        if not self.isConnected():
            return 0
        
        # Count vertices with odd degree
        odd = 0
        for node in self.graph.keys():
            if len(self.graph[node]) % 2 != 0:
                odd += 1

        '''If odd count is 2, then semi-eulerian.
        If odd count is 0, then eulerian
        If count is more than 2, then graph is not Eulerian
        Note that odd count can never be 1 for undirected graph'''
        if odd == 0:
            return 2
        elif odd == 2:
            return 1
        else:
            return 0

    # Function to run test cases
    def test(self):
        res = self.isEulerian()
        if res == 0:
            print("graph is not Eulerian")
        elif res == 1:
            print("graph has a Euler path")
        else:
            print("graph has a Euler circuit")

# Test case 1: Expected output "graph has a Euler circuit"
ln1 = [1, 2, 1, 6, 2, 3, 3, 4, 4, 5, 5, 6]
# ln1 = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 1, 2, 1, 4, 1, 5, 2, 3, 2, 4, 3, 5, 4, 5] #euler path
# ln1 = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 3, 2, 5, 2, 6, 3, 4, 3, 5, 4, 6, 5, 6] #euler path

g1 = Graph()
i = 0
while i < len(ln1):
    g1.addEdge(ln1[i], ln1[i+1])
    i += 2
g1.test()

问题分析与修复点 #

1. 移除固定顶点数限制，适配任意节点编号 #

原代码中Graph类初始化需要传入顶点数，强制要求节点编号是从0开始的连续整数，但你的测试用例节点是1-6，导致：

• 遍历range(self.V)时完全漏掉了实际存在的节点1-6
• visited数组长度不足，访问编号大于self.V-1的节点会触发索引越界

修复：

• 去掉self.V属性，改用self.graph.keys()获取所有实际存在的节点
• visited改用字典存储，完美适配任意非连续节点编号

2. 连通性检查的起始节点判断错误 #

原代码中寻找DFS起始节点的条件是len(self.graph[i]) > 1，这会漏掉度数为1的节点（比如欧拉路径的端点），导致无法正确启动连通性检查。

修复：

• 改为len(self.graph[node]) > 0，只要是有边的节点都可以作为DFS的起始点

3. 度数统计的遍历范围错误 #

原代码中遍历range(self.V)统计度数，完全没覆盖到实际的节点1-6，导致度数统计结果完全错误。

修复：

• 遍历self.graph.keys()统计所有实际存在节点的度数，确保计数准确

4. 简化边的添加逻辑 #

原代码用两个变量i和j遍历边列表，逻辑冗余，改为单变量i每次递增2，代码更简洁易读。

5. 统一输出文本 #

把原代码中的“graph has a Euler cycle”改为“graph has a Euler circuit”，匹配你的预期输出术语。

运行修复后的代码，测试用例ln1会正确输出graph has a Euler circuit。

内容的提问来源于stack exchange，提问作者Matthew