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变成了一个集合，而不是一个列表，因为检查一个集合的成员资格更快。