寻找欧拉之旅

Question

我正在尝试解决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 find_eulerian_tour(graph):
    tour = []

    start_vertex = graph[0][0]
    tour.append(start_vertex)

    while len(graph) > 0:
        current_vertex = tour[len(tour) - 1]
        for edge in graph:
            if current_vertex in edge:
                if edge[0] == current_vertex:
                    current_vertex = edge[1]
                elif edge[1] == current_vertex:
                    current_vertex = edge[0]
                else:
                    # Edit to account for case no tour is possible
                    return False

                graph.remove(edge)
                tour.append(current_vertex)
                break
    return tour

graph = [(1, 2), (2, 3), (3, 1)]
print find_eulerian_tour(graph)

>> [1, 2, 3, 1]

然而，当我提交这篇文章时，我被评分员拒绝了。我做错了什么吗？我看不到任何错误。

Answer 1

下面是你的算法失败的一个有效案例：

graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]

使用print的强大功能来了解graph和current_vertex发生了什么。

另一个提示:向下移动else，使其属于for，并在for循环未中断时执行。就像现在一样，它永远不会被执行。当然，在校正之后，算法仍然失败。

当然，算法仍然失败。

当然，算法仍然失败。

请不要评论说代码不能工作。算法仍然失败，即使下面的代码做了OP想要做的事情。重点是要证明OP的算法是错误的，而OP无法确定。为此，需要正确实现OP的算法(见下文)。错误算法的正确实现仍然不是正确的解决方案。

很抱歉，我写了这些冗长的解释，让这个答案变得更糟，但人们继续抱怨代码不能工作(当然，重点是要证明它是错误的)。他们也对这个答案投了反对票，可能是因为他们希望能够复制代码作为解决方案。但这不是重点，重点是要向操作员表明他的算法中存在错误。

下面的代码找不到欧拉之旅。看看其他地方，复制代码来传递你的评估！

def find_eulerian_tour(graph):
    tour = []

    current_vertex = graph[0][0]
    tour.append(current_vertex)

    while len(graph) > 0:
        print(graph, current_vertex)
        for edge in graph:
            if current_vertex in edge:
                if edge[0] == current_vertex:
                    current_vertex = edge[1]
                else:
                    current_vertex = edge[0]

                graph.remove(edge)
                tour.append(current_vertex)
                break
        else:
            # Edit to account for case no tour is possible
            return False
    return tour

graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
print(find_eulerian_tour(graph))

输出：

[(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)] 1
[(2, 3), (3, 1), (3, 4), (4, 3)] 2
[(3, 1), (3, 4), (4, 3)] 3
[(3, 4), (4, 3)] 1
False

Answer 2

我也在同一堂课上，WolframH的答案对我不起作用。以下是我的解决方案(已被评分员接受)：

将所有可能的next node放入一个堆(search)中，然后在记录时逐个搜索它们。

def next_node(edge, current):
    return edge[0] if current == edge[1] else edge[1]

def remove_edge(raw_list, discard):
    return [item for item in raw_list if item != discard]

def find_eulerian_tour(graph):
    search = [[[], graph[0][0], graph]]
    while search:
        path, node, unexplore = search.pop()
        path += [node]

        if not unexplore:
            return path

        for edge in unexplore:
            if node in edge:
                search += [[path, next_node(edge, node), remove_edge(unexplore, edge)]]

if __name__ == '__main__':
    graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
    print find_eulerian_tour(graph)

1、3、4、3、2、1

Answer 3

这里有一个你的算法不能处理的情况:4个顶点上的完整图。把一个print tour放在里面，你会得到：

>>> cg4 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
>>> find_eulerian_tour(cg4)
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 0]
[0, 1, 2, 0, 3]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[etc.]

我将留给您自己找出方法的问题--您可以很容易地在google上搜索完整的实现，因此，既然您没有这样做，我假设您想要自己找出解决问题的乐趣。:^)

编辑：

嗯。我承认，一开始我认为这只是一个失败的案例。无论如何，@WolframH先于我更新了一个示例，但您也可以查看5个顶点上的完整图，其中您的代码给出了

[0, 1, 2, 0, 3, 1, 4, 0]

并且丢失边缘(2,3)、(2,4)和(3,4)。