检查图形是否为 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我是递归的新手。我想了解为什么我的函数返回 none 因为这些知识稍后会对我有所帮助 :) 提前致谢。

Answer 1

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

return dfs(nei,c^1)

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

return dfs(node)

在您的 possibleBipartition() 函数中。

请注意，您需要在 Python 中明确指定 return，如果在 Racket 和 Haskell.

等语言中有一个不同之处

Answer 2

从表面上看，函数returns None因为你没有return声明。所以函数 possibleBipartition 没有 return 任何东西（即 None）。这只是 python 允许您在没有任何错误的情况下执行的语法操作，这可能会让新手感到困惑。您将需要 return 函数中的某些内容，以便您的打印语句不只是打印 None。当且仅当 possibleBipartition 有效时，一个好主意可能是 return True。

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

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

checking if the graph is bipartite.why is my function returning none?

python

recursion

graph

depth-first-search