判断给定图为欧拉图/半欧拉图：Python代码末尾判断逻辑失效求助

Hey there! 作为Python初学者碰到这种卡壳的情况太正常啦，别慌～先从半欧拉图的核心规则入手，再一步步补全你的代码。

首先明确半欧拉图的判定规则（无向图） #

要判断一个无向图是不是半欧拉图（存在欧拉路径但不存在欧拉回路），必须同时满足两个条件：

• 整个图是连通的（所有节点之间都能通过路径互相到达）
• 图中恰好有2个奇数度的节点（度数=节点连接的边数）

补充：如果是0个奇数度节点，那是欧拉图（存在欧拉回路，也属于有欧拉路径，但通常半欧拉图特指只有路径没有回路的情况）

先分析你给出的图结构 #

先帮你算一下每个节点的度数：

graph = { 
    "1" : set(["2", "6"]),  # 度数2（偶）
    "2" : set(["1", "6", "7", "3"]),  # 度数4（偶）
    "3" : set(["2","7","4", "5"]),  # 度数4（偶）
    "4" : set(["3", "5"]),  # 度数2（偶）
    "5" : set(["3","4", "7", "6"]),  # 度数4（偶）
    "6" : set(["1","2", "7", "5"]),  # 度数4（偶）
    "7" : set(["2", "3", "5"]),  # 度数3（奇）
}

这里有个小问题：无向图的总度数一定是偶数（每条边被两个节点各算一次），但你这个图的总度数是 2+4+4+2+4+4+3=23（奇数），说明图的边可能写错了？比如节点7是不是漏了一个邻居？不过没关系，咱们先把代码逻辑写对，图的问题你可以自己调整～

补全你的代码，实现判定逻辑 #

你的path函数看起来是用来做深度优先搜索（DFS）判断连通性的，我帮你补全并搭配完整的判定流程：

步骤1：实现DFS遍历，判断图是否连通 #

这个函数会遍历从起始节点出发能到达的所有节点，标记到visited集合里：

def dfs(graph, node, visited):
    visited.add(node)
    # 遍历当前节点的所有邻居
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def is_connected(graph):
    if not graph:
        return True
    # 取第一个节点作为起始点
    start_node = next(iter(graph.keys()))
    visited = set()
    dfs(graph, start_node, visited)
    # 如果所有节点都被访问到，说明图是连通的
    return len(visited) == len(graph)

步骤2：统计奇数度节点的数量 #

def count_odd_degree_nodes(graph):
    count = 0
    for node in graph:
        degree = len(graph[node])
        if degree % 2 != 0:
            count += 1
    return count

步骤3：最终判定是否为半欧拉图 #

def is_semi_eulerian(graph):
    if not is_connected(graph):
        return False
    odd_count = count_odd_degree_nodes(graph)
    # 半欧拉图需要恰好2个奇数度节点
    return odd_count == 2

测试一下 #

我调整了你的图，让它符合无向图的合法性（总度数为偶数，且有2个奇数度节点）：

# 调整后的合法无向图（两个奇数度节点：5和6）
graph_fixed = { 
    "1" : set(["2", "6"]),
    "2" : set(["1", "6", "7", "3"]),
    "3" : set(["2","7","4", "5"]),
    "4" : set(["3", "5"]),
    "5" : set(["3","4", "6"]),  # 度数3（奇）
    "6" : set(["1","2", "5"]),  # 度数3（奇）
    "7" : set(["2", "3"]),  # 度数2（偶）
}

print(is_semi_eulerian(graph_fixed))  # 输出True，符合半欧拉图条件

给初学者的小提示 #

• 写图相关的代码时，先确认图的合法性（无向图总度数为偶数），避免因为输入错误导致逻辑混乱
• 连通性判断除了DFS，也可以用BFS（广度优先搜索），逻辑类似，只是遍历顺序不同
• 如果是有向图，半欧拉图的判定规则不一样，不过看你的图结构应该是无向图，所以就不展开啦

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