检查图形是否为二分图.为什么我的函数返回 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))

许多解决方案可在线获得。但我是递归的新手。我想了解为什么我的函数返回 none ，因为知识将在以后帮助我:) 提前谢谢。

Answer 1

似乎它返回 None 是因为您的代码中没有return ...。我会确保你明确地回到你需要的地方。例如，您可能希望添加 return 语句的两个位置：

return dfs(nei,c^1)

在您的dfs()功能以及：

return dfs(node)

在您的possibleBipartition()函数中。

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

Answer 2

表面上，该函数返回None，因为您没有 return 语句。所以函数 possibleBipartition 不返回任何内容(即 None(。这只是python允许你没有任何错误的语法问题，这可能会让新人感到困惑。您将需要从函数返回一些内容，以便您的 print 语句不只是打印None.一个好主意可能是当且仅当可能的双分区有效时返回 True。

你可以进行的一个调整是检查你在函数中构建的颜色字典，看看"possibleBipartition"是否有效。这可以通过了解以下事实来实现：图形具有有效的二分法，因为每个顶点仅属于一种颜色(在您的情况下为 0 或 1(。