C++ 检查给定图是否使用DFS为双向图

什么是DFS和双向图

在开始讨论如何使用DFS检查图的性质之前，我们先来了解一下DFS和双向图的概念。

DFS（Depth First Search，深度优先搜索）是图遍历的一种常见算法。在DFS中，我们从某个顶点开始遍历，遍历到它的一个邻接点，然后再以这个邻接点为起点进行递归遍历。这样不断递归遍历下去，直到遍历完整个图。

双向图是指一个无向图中，存在一种节点分成两个部分的情况，每个节点的两个部分互相连接，且没有一对相邻的节点是同一部分的。也就是说，双向图的节点可以分为两类，每类中的节点之间没有边相连，而不同类中的节点之间都有边相连。

如何检查给定图是否使用DFS为双向图

为了方便起见，我们先定义一个图的类，用来表示一个图及其一些基本属性，比如节点个数、边集等。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

这里我们使用Python的collections模块中的defaultdict类来表示graph属性，defaultdict的好处是可以在访问不存在的键时自动创建该键，并赋予一个默认值。这里我们的默认值为列表类型。

接下来，我们用DFS遍历该图并标记每个节点的“颜色”。在这里，我们定义“白色”表示该节点还没有被遍历，颜色将在DFS的过程中变为“灰色”，表示该节点正在被遍历，最后变为“黑色”，表示该节点已经被遍历。

def DFS(self, v, color):
        color[v] = "gray"

        for i in self.graph[v]:
            if color[i] == "white":
                DFS(self, i, color)
            elif color[i] == "gray":
                return False

        color[v] = "black"
        return True

在DFS的过程中，如果我们发现某个节点和其邻接节点都被标记成“灰色”，那么就说明该图不可能是双向图。这是因为如果存在一对相邻的节点是同一部分的，那么它们的颜色都应该是“黑色”，但是由于DFS的遍历方式，它们都会先被标记成“灰色”，从而导致一个节点无法被标记成“黑色”。

于是，我们可以将所有节点标记成“白色”，然后循环DFS遍历所有节点。如果DFS算法没有返回False，则说明该图可以使用DFS来表示为双向图。

def is_bipartite(self):
        color = ["white" for i in range(self.V)]

        for i in range(self.V):
            if color[i] == "white":
                if not self.DFS(i, color):
                    return False

        return True

以上代码即为检查给定图是否使用DFS为双向图的完整代码。