Проблема с возвращением bool из рекурсивной функции - PullRequest
Новая
       8

Проблема с возвращением bool из рекурсивной функции

0 голосов
/ 19 октября 2018

Я работаю над проблемой домашней работы, в которой мы должны написать алгоритм, который может определить, является ли график двудольным или нет.Мое решение на python работает, но сейчас оно выдает исключение, если график не является двудольным, вместо этого я хотел бы, чтобы он возвращал логическое значение.Как я мог изменить этот код?

def is_bipartite(v, visited, colors, counter):

    print(v)

    # Set this vertex to visited
    visited[v] = True
    colors[v] = counter % 2

    # Explore links
    for u in v.links:

        # If linked up node u has already been visited, check its color to see if it breaks
        # the bipartite of the graph
        if u in visited:

            if colors[v] == colors[u]:

                raise Exception("Not Bipartite")

        # If the link has not be visited then visit it
        if u not in visited:

            visited[u] = False

            is_bipartite(u, visited, colors, counter + 1)

1 Ответ

0 голосов
/ 19 октября 2018

Если я правильно понимаю ваш код, вы хотите вернуть False, если в любом месте вашего рекурсивного поиска вы найдете совпадающие цвета.Вы хотите вернуть True, если дойдете до конца поиска, не найдя ничего.

Это не так уж сложно сделать.Просто измените оператор raise на return False, проверьте результат рекурсивных вызовов и верните False, если любой из них вернет результат False.Затем просто поставьте return True в конце функции, и все готово: 

def is_bipartite(v, visited, colors, counter):
    visited[v] = True
    colors[v] = counter % 2
    for u in v.links:
        if u in visited:
            if colors[v] == colors[u]:
                return False                # return instead of raise in this base case

        if u not in visited:
            visited[u] = False
            if not is_bipartite(u, visited, colors, counter + 1): # check the recursion
                return False                                      # pass on any False

    return True  # return True only if you got to the end without returning False above
...