寻找欧拉之旅

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的算法(见下文).错误算法的正确实现仍然不是正确的解决方案.

我很遗憾通过编写所有这些冗长的解释来使这个答案变得更糟,但人们继续抱怨代码不起作用(当然,重点是表明它是错误的).他们也赞成这个答案,可能是因为他们希望能够将代码复制为解决方案.但这不是重点,重点是向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