检查图形是否为bipartite.why ?我的函数是否返回none？

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))

许多解决方案都是可用的，online.But我对递归是个新手。我想知道为什么我的函数不返回任何内容，因为这些知识稍后会对我有所帮助:)提前谢谢。

Answer 1

看起来它返回了None，因为你的代码中没有return ...。我会确保你显式地返回你需要的地方。例如，您可能希望添加返回语句的两个点：

return dfs(nei,c^1)

在您的dfs()函数中以及：

return dfs(node)

在您的possibleBipartition()函数中。

请注意，如果Python中有返回值，则需要显式指定该返回值，这与Racket和Haskell等语言不同。

Answer 2

从表面上看，该函数返回None，因为没有return语句。因此，函数possibleBipartition不会返回任何内容(即None)。这只是一个语法问题，python允许您在没有任何错误的情况下完成这项工作，这可能会让新手感到困惑。为了让打印语句不仅仅打印None，您需要从函数中返回一些内容。当且仅当possibleBipartition有效时，返回True可能是一个好主意。

您可以尝试的一个调整是检查您在函数中构建的颜色字典，以查看"possibleBipartition“是否有效。这可以在知道以下事实的情况下实现:一个图有一个有效的二分当且仅当每个顶点只属于一种颜色(在你的例子中是0或1)。