无法从递归函数返回 bool

Question

我正在处理一个家庭作业问题，我们必须编写一个算法来确定一个图是否是二分图。我的 python 解决方案有效，但现在如果图形不是二分的，它会抛出异常，相反我希望它成为 return 一个布尔值。我该如何修改这段代码？

def is_bipartite(v, visited, colors, counter):

    print(v)

    # Set this vertex to visited
    visited[v] = True
    colors[v] = counter % 2

    # Explore links
    for u in v.links:

        # If linked up node u has already been visited, check its color to see if it breaks
        # the bipartite of the graph
        if u in visited:

            if colors[v] == colors[u]:

                raise Exception("Not Bipartite")

        # If the link has not be visited then visit it
        if u not in visited:

            visited[u] = False

            is_bipartite(u, visited, colors, counter + 1)

Answer 1

如果我对你的代码的理解正确，你想要 return False 如果你在递归搜索的任何地方得到匹配的颜色。如果您到达搜索的结尾而没有找到任何内容，您想要 return True。

这并不难做到。只需将 raise 语句更改为 return False 并检查递归调用的结果，并且 return False 如果其中任何一个 return a False结果。然后只需将 return True 放在函数的末尾即可：

def is_bipartite(v, visited, colors, counter):
    visited[v] = True
    colors[v] = counter % 2
    for u in v.links:
        if u in visited:
            if colors[v] == colors[u]:
                return False                # return instead of raise in this base case

        if u not in visited:
            visited[u] = False
            if not is_bipartite(u, visited, colors, counter + 1): # check the recursion
                return False                                      # pass on any False

    return True  # return True only if you got to the end without returning False above

无法从递归函数返回 bool

Trouble returning bool from recursive function

python

recursion

graph-theory