檢查圖形是否為二段式，為什麼我的函數會返回無？

Question

import collections
class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            for nei in graph[node]:
                dfs(nei,c^1)

        for node in range(1, N+1):
            if node not in color:
                dfs(node)
g=Solution()
N=3
dislikes=[[1,2],[2,3]]
print(g.possibleBipartition(N, dislikes))

网上有很多解决方法，但我对递归是个新手，我想了解一下为什么我的函数返回无，因为这些知识对我以后有帮助:)谢谢。我想了解为什么我的函数返回无，因为这些知识对我以后有帮助:)先谢谢你。

Answer 1

似乎它返回的是 None，因为你没有一个 return ... 在你代码中的任何地方。我会确保你在你需要的地方明确地返回。例如，有两个地方你可能需要添加一个返回语句。

return dfs(nei,c^1)

在你的 dfs() 功能以及。

return dfs(node)

在你的 possibleBipartition() 函数。

请注意，在Python中，如果有返回，你需要显式地指定返回，而不像在Racket和Haskell等语言中。

Answer 2

从表面上看，函数返回的是 None 因为你没有返回语句。所以函数 possibleBipartition 没有返回任何东西（即 None）。这只是python允许你在没有任何错误的情况下进行的语法操作，这可能会让新人感到困惑。你需要从你的函数中返回一些东西，以便你的 print 语句不只是 print None. 一个好的想法可能是，如果且仅当 possibleBipartition 有效时才返回 True。

你可以做的一个调整是检查你在函数中建立的color dict，看看 "possibleBipartition "是否有效。这可以通过以下事实来实现：如果一个图的每个顶点只属于一种颜色（在你的例子中是0或1），那么这个图就有一个有效的二分法。