785.判断二分图

https://leetcode-cn.com/problems/is-graph-bipartite/

一、dfs

class Solution:
    def isBipartite(self, graph) -> bool:
        self.flag = True
        n = len(graph)  # 顶点数
        visited = [False] * n
        color = [False] * n     #true,false分别表示不同颜色
        def dfs(v):
            if not self.flag:    # 已经找到不是二分图的部分，不用再继续遍历，直接返回
                return
            visited[v] = True
            # 递归访问所有邻点
            for j in graph[v]:
                # 若未访问过，标记与当前节点不同的颜色
                if not visited[j]:
                    color[j] = not color[v]
                    dfs(j)
                # 已访问过，若当前节点颜色相同，说明不是二分图
                else:
                    if color[j] == color[v]:
                        self.flag = False

        # 因为图不一定是联通的，可能存在多个子图
        # 所以要把每个节点都作为起点进行一次遍历
        # 如果发现任何一个子图不是二分图，整幅图都不算二分图
        for i in range(n):
            if not visited[i]:
                dfs(i)
        return self.flag

二、bfs

但是效率不如dfs

import queue
class Solution:
    def isBipartite(self, graph) -> bool:
        self.flag = True
        n = len(graph)  # 顶点数
        visited = [False] * n
        color = [False] * n     #true,false分别表示不同颜色

        def bfs(v):
            q = queue.Queue()   #队列
            q.put(v)
            visited[v] = True
            while self.flag and (not q.empty()):
                for _ in range(q.qsize()):
                    cur = q.get()
                    # 遍历当前结点的所有相邻结点，若未访问则加入队列
                    for j in graph[cur]:
                        if not visited[j]:
                            color[j] = not color[cur]
                            visited[j] = True
                            q.put(j)
                        else:
                            if color[j] == color[cur]:
                                self.flag = False

        # 因为图不一定是联通的，可能存在多个子图
        # 所以要把每个节点都作为起点进行一次遍历
        # 如果发现任何一个子图不是二分图，整幅图都不算二分图
        for i in range(n):
            if not visited[i]:
                bfs(i)
        return self.flag