使用dfs检查图是否为二部图

使用DFS检查图是否为二部图是一种常见的图论问题。二部图是指能够将图的所有顶点分为两个不相交的集合，使得图中的每条边的两个顶点分别属于这两个集合。

具体的算法步骤如下：

选择一个起始顶点作为根节点，并将其标记为集合A。
对于根节点的每个邻接顶点，将其标记为集合B。
对于集合B中的每个顶点，将其邻接顶点标记为集合A。
重复步骤3，直到所有顶点都被标记为集合A或集合B。
如果在标记的过程中发现某个顶点的邻接顶点已经被标记为同一个集合，则该图不是二部图。
如果所有顶点都被正确地标记为集合A或集合B，则该图是二部图。

以下是使用DFS检查图是否为二部图的Python代码示例：

def isBipartite(graph):
    n = len(graph)
    colors = [0] * n  # 0表示未标记，1表示集合A，-1表示集合B

    def dfs(node, color):
        colors[node] = color
        for neighbor in graph[node]:
            if colors[neighbor] == color:
                return False
            if colors[neighbor] == 0 and not dfs(neighbor, -color):
                return False
        return True

    for i in range(n):
        if colors[i] == 0 and not dfs(i, 1):
            return False
    return True

该算法的时间复杂度为O(V + E)，其中V是顶点数，E是边数。

二部图的应用场景包括社交网络中的好友关系划分、任务调度问题、图像分割等。

腾讯云相关产品中，与图计算相关的产品有腾讯云图数据库 Neptune，它是一种高性能、高可靠、全托管的图数据库，适用于存储和查询大规模图数据。详情请参考腾讯云图数据库 Neptune的产品介绍：https://cloud.tencent.com/product/neptune。