Python: Нахождение двудольного графа с помощью DFS

Question

Я пытаюсь преобразовать программу DFS, чтобы проверить, является ли график двудольным.Я хочу пройти путь и отправить посещенные узлы в разные подмножества, поскольку они не являются смежными.Например:

если путь будет выглядеть следующим образом: 1-> 2-> 3-> 4-> 5

Два подмножества должны выглядеть следующим образом:

[1,3,5] [2,4]

А вот код DFS:

def dfs(x, node, visited):
if node not in visited:
    visited.append(node)
    for n in x[node]:
        dfs(x,n, visited)
return visited

Answer 1

Тестирование на двухсторонность выполняется путем «окрашивания» смежных узлов чередующимися цветами во время выполнения DFS, и, если какие-либо два цвета имеют одинаковый «цвет», тогда график не является двудольным.Вы можете сделать это, поместив узлы в два разных набора при выполнении DFS следующим образом:

def bipart(x, node, visited, set1, set2):
    if node in set2:                   # if a node has already been put into the other set, the graph is not bipartite
        return False
    if node not in visited:            # if we haven't seen this yet
        visited.add(node)              # mark it as visited
        set1.add(node)                 # put it in the first set
        for n in x[node]:              # for each neighbor
            bipart(x, n, set2, set1)   # put it into the other set
    return True                        # if we get here we have separated the graph into two sets where all the neighbors of a node in one set are in the other set.

Обратите внимание, что я сделал visited набор вместо списка, потому что быстрее проверять членство вустановлен.