python - 查找Eulerian Tour的Python代码在一种情况下不起作用。为什么？

This question already has answers here:

Finding a Eulerian Tour
（10个答案）
5年前关闭。
我试图解决一个关于Udacity的问题，描述如下：

# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

我写的代码如下。它不太优雅，但似乎能起到作用。

def getCurPoint(points, curPoint):
    for pair in range(len(points)):
        if curPoint in points[pair]:
            for i in points[pair]:
                if i != curPoint:
                    points.pop(pair)
                    return [curPoint] + getCurPoint(points, i)
    return []

def takeTour(graph):
    point = graph[0][0]
    criticals = []
    points = []
    for pair in range(len(graph)):
        if point in graph[pair] and len(criticals) <= 1:
            criticals.append(graph[pair])
        else:
            points.append(graph[pair])

    stops = [point]

    curPoint = criticals[0][1]

    stops += getCurPoint(points, curPoint)

    for x in criticals[1]:
        if x != point:
            stops.append(x)

    stops.append(point)

    return stops

问题是，当我提交代码时，除了graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
你知道为什么考试不及格吗？（如果你有让代码更优雅的技巧，我很乐意听到！）

最佳答案

您在getCurPoint()中没有回溯机制。这意味着您的算法将获取在图中找到的第一条移动的边，构建一条可能导致死胡同的路径，而不必遍历所有节点。
这正是你的例子所发生的事情。你的算法将从node0开始到node1。此节点提供3条边以继续您的旅行（分别是(1, 5)，(1, 7)，(1, 6)），但其中一条边将导致死胡同而不完成欧拉旅行。不幸的是，图定义中列出的第一条边是错误的路径，不允许您访问节点(1, 5)、6和3。
为了检查我的确认，您可以尝试更改图的给定定义，以使用7反转边(1, 5)，并查看您的算法将如何正确列出所有节点。
我能帮忙吗
首先，为了帮助您自己解决这些问题，您应该始终制作图表（而不仅仅是让Feynman高兴），并尝试在图表上遵循您的算法。这些例子很容易画出来，很明显算法是不正确的，你可能会发现原因。
其次，这个练习是关于回溯。你知道这是什么吗？如果没有，你可以尝试用谷歌搜索这个词，甚至可以在stackoverflow搜索框中搜索它，维基百科也有一篇关于这个的好文章。
最后，我可以给你一些关于你的编码风格的建议。请将其视为私人物品，并采取适合您当前需求的措施：
如果可能：
如果只在之后使用(1, 7)，请避免使用for x in range(len(graph)):。蟒蛇
提供非常优雅的替换解决方案。如果你真的
需要迭代元素的索引，可以选择优雅的：
graph[x]
避免你的三行结构（你已经使用了两次）涉及到
for edge in graph:：

for x in criticals[1]:
    if x != point:
        stops.append(x)

更喜欢显式，更小：

node_a, node_b = critical_edges[1] 
stops += [node_a] if node_b == node else [node_b]

不太重要的代码外观风格备注：
避免对变量、函数名和方法名使用java CamelCase，python有
PEP8打开
更喜欢变量名而不是使用小写和下划线的样式。
将“point”重命名为“node”，以保留图形上更广泛使用的词汇表
将“pair”重命名为“edge”，以获取
变量的含义而不是它的类型（尽管您可以想到
将两种信息混合在一起称为“AA>”
应用这些修饰性的注释，我们将把例如for i, edge in enumerate(graph):重命名为if，其中：
变量_带有_下划线，而不是CamelCase和for>getCurPoint如前所述，
复数，因为它将返回一个节点列表
“cur”被重命名为“next”，因为它是关于获取下一个节点的。
以一种更像蟒蛇的方式重写代码的示例
请注意，这只是一个重写，而且以前的错误始终存在。看看get_next_nodes函数的变化：

def get_next_nodes(edges, cur_node):
    connected_edges = [x for x in edges
                       if cur_node in x]
    if connected_edges:
        a, b = connected_edges[0]
        next_node = b if a == cur_node else a
        edges.remove(connected_edges[0])
        return [cur_node] + get_next_nodes(edges, next_node)
    return []

def take_tour(graph):
    start_node = graph[0][0]
    critical_edges = []
    nodes = []
    for edge in graph:
        if start_node in edge and len(critical_edges) < 2:
            critical_edges.append(edge)
        else:
            nodes.append(edge)

    second_node = critical_edges[0][1]
    stops = [start_node] + get_next_nodes(nodes, second_node)

    a, b = critical_edges[1]
    stops += [a] if b == start_node else [b]
    return stops + [start_node]

现在，你的算法有更多的问题
你的脚本应该如何反应非欧拉图？您的算法将输出各种各样的结果，从错误的节点列表到令人困惑的异常。如果无法避免异常，则应引发适当的非混淆异常。使用以下图表尝试您的算法：
非欧拉语：
[（0，1），（1，5），（1，7），（4，5），
（4，8），（1，6），（3，7），（5，9），
（2，4），（2，5），（3，6），（8，9）]
非欧拉语：Point
欧拉语：nodes
非欧拉语：get_next_nodes()
您正在[(0, 1), (0, 3)]中手动添加列表中的3个节点。有一个更优雅的解决方案，用更少的代码！
为什么要在[(0, 0)]中选择一个结束边和开始边？你可能选错了！你看到在多项选择中选第一可能是错误的。尝试此图：
欧拉语：[]，正确的结果应该是take_tour。
最后，让met给你一个正确的答案
这个简单的递归代码将回答您试图解决的初始问题。
请注意，初始的take_tour距离回溯不远。
唯一的增加是引入了[(0, 1), (0, 1), (0, 2), (0, 2)]循环，它将尽可能地解析
解决方案，而不是盲目地采取第一个。
但要允许回溯，函数必须能够退出当前路径计算。这个
在没有找到路径的情况下允许返回[0, 1, 0, 2, 0]值。getCurPoint将从子函数调用重新执行到父函数，有效地取消绑定递归，直到它可以尝试另一条边，这要归功于for循环。
您会注意到您可以合并False和False。这使得添加的实益实体在新的for中隐藏了两个特性：
它将能够向您显示欧拉路径（这不同于欧拉之旅，后者必须在同一节点上开始和结束）。
如果您有足够的好奇心来强制另一个开始节点查看路径，则可以提供一个开始节点。
代码如下：

def take_tour(graph, node_start=None, cycle_only=True):
    if len(graph) == 0:
        if node_start is None:
            return []
        return [node_start]

    node_start = graph[0][0] if node_start is None else node_start

    for chosen_edge in [x for x in graph if node_start in x]:
        (node_a, node_b) = chosen_edge
        path = take_tour([e for e in graph if e != chosen_edge],
                         node_b if node_start == node_a else node_a,
                         cycle_only=False)
        if path is not False and (not cycle_only or node_start == path[-1]):
            return [node_start] + path
    return False

如果您正在寻找其他一些简单的练习，这里有两个简单易懂的问题可以一次回答：
如何修改getCurPoint以返回所有可能的路线/路径的列表？
您是否能够在所有可能的巡回/路径的迭代器中转换take_tour？（一个聪明的迭代器，它只能根据请求计算下一个路径）。
我希望这足够说教了。

关于python - 查找Eulerian Tour的Python代码在一种情况下不起作用。为什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13435413/

上一篇：python - 我可以在没有使用 python 打开实际浏览器的情况下将 selenium 与 Scrapy 一起使用吗

下一篇：python - 在 python 的 str 方法中返回或打印

相关文章：

python - 避免 SQLAlchemy 中的套接字超时

python - 循环绘图，仅获取最后一个绘图

Ruby:如何从嵌套哈希中删除 nil/empty 值，为什么我没有尝试这样做？

recursion - 带有子图聚合的递归查询(任意深度)

Python - 将 mysql 时间戳类型转换为 matplotlib 和图表

python - 查找 2 个 pandas 数据帧的行之间的差异

python - 如何设置 Odoo 智能按钮的顺序？

Javascript 递归标准化 JSON 数据

batch-file - 批处理 - 计算当前文件夹和子文件夹中文件的行数

haskell - 折叠是左尾递归吗？