проверка двудольного графа. почему моя функция ничего не возвращает? - PullRequest
Новая
       79

проверка двудольного графа. почему моя функция ничего не возвращает?

0 голосов
/ 29 мая 2020 
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))

Многочисленные решения доступны в Интернете, но я новичок в рекурсии. Я хочу понять, почему моя функция не возвращает ничего, поскольку эти знания мне позже помогут :) Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 29 мая 2020

На поверхности функция возвращает None, потому что у вас нет оператора возврата. Таким образом, функция possibleBipartition ничего не возвращает (т.е. None). Это всего лишь синтаксис, который python позволяет вам обойтись без ошибок, которые могут сбить с толку новых людей. Вам нужно будет что-то вернуть из вашей функции, чтобы ваш оператор print не просто печатал None. Хорошей идеей может быть возвращение True тогда и только тогда, когда значение possibleBipartition действительно. . Этого можно достичь, зная следующий факт: граф имеет допустимую бипаритизацию, если каждая вершина принадлежит только одному цвету (0 или 1 в вашем случае).

0 голосов
/ 29 мая 2020

Кажется, он возвращает None, поскольку в вашем коде нет return .... Я бы удостоверился, что вы явным образом вернетесь туда, куда вам нужно. Например, два места, в которые вы можете добавить оператор возврата: 

return dfs(nei,c^1)

в вашей функции dfs(), а также: 

return dfs(node)

в вашей функции possibleBipartition().

Обратите внимание, что вам нужно явно указать возврат в Python, если он не похож на такие языки, как Racket и Haskell.

...