leetcode 785. 判斷二分圖

785. 判斷二分圖

給定一個無向圖graph，當這個圖為二分圖時傳回true。

如果我們能将一個圖的節點集合分割成兩個獨立的子集A和B，并使圖中的每一條邊的兩個節點一個來自A集合，一個來自B集合，我們就将這個圖稱為二分圖。

graph将會以鄰接表方式給出，graph[i]表示圖中與節點i相連的所有節點。每個節點都是一個在0到graph.length-1之間的整數。這圖中沒有自環和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重複的值。

示例 1:

輸入: [[1,3], [0,2], [1,3], [0,2]]

輸出: true

解釋:

無向圖如下:

0----1
										|    |
										|    |
										3----2
           

我們可以将節點分成兩組: {0, 2} 和 {1, 3}。

示例 2:

輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]

輸出: false

解釋:

無向圖如下:

0----1
										| \  |
										|  \ |
										3----2
           

我們不能将節點分割成兩個獨立的子集。

注意:

graph 的長度範圍為 [1, 100]。

graph[i] 中的元素的範圍為 [0, graph.length - 1]。

graph[i] 不會包含 i 或者有重複的值。

圖是無向的: 如果j 在 graph[i]裡邊, 那麼 i 也會在 graph[j]裡邊。

深度優先搜尋

每一次都染色一個之後與其相接的點進行染色判斷，先找到一個沒被染色的節點u，把它染上一種顔色，之後周遊所有與它相連的節點v，如果節點v已被染色并且顔色和節點u一樣，那麼就不是二分圖。如果這個節點v沒有被染色，先把它染成與節點u不同顔色的顔色，然後周遊所有與節點v相連的節點…如此遞歸下去。

from typing import List
##深度優先搜尋，每一次都染色一個之後鬥魚其相接的點進行染色判斷
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)#計算有多少個點
        UNCOLORED, RED, BLUE = 0, 1, 2#設定三種顔色
        record = [UNCOLORED] * (n)#為這些點建立一個清單，記錄他們的顔色
        valid = True#初始化預設是可分的

        #用于檢驗目前染色是否符合要求
        def dfs(i, color):
            nonlocal valid
            record[i] = color#将目前點進行染色
            dif_color = BLUE if color == RED else RED#取一個相反的顔色
            for j in range(len(graph[i])):#對本次染色點的鄰接點進行染色判斷
                if record[graph[i][j]] == UNCOLORED:#緊鄰點如果無色，進行染相反色，然後再次遞歸
                    dfs(graph[i][j],dif_color)
                    if valid == False:##這裡很重要，遞歸之後對valid進行判斷，如果為False,放棄遞歸，直接傳回
                        return#是以每當遞歸的過程中出現了一個False之後，就會從這裡，一步一步往上跳出程式
                elif record[graph[i][j]] == dif_color:#鄰接點已經染了相反顔色，繼續下一個鄰接點判斷
                    continue
                else:#如果鄰接點染的相同顔色，valid 指派 False,傳回本次遞歸
                    valid = False
                    return 

        for i in range(n):#對n個點進行循環判斷
            if record[i] == UNCOLORED:#如果沒有被染色，那麼将其然染色後進行判斷
                dfs(i, RED)#深度優先判斷，如果不可分，則會将valid指派為False
                if valid == False:#隻要傳回一個False,那麼程式結束
                    break
        return valid

###########  DFS簡潔寫法
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        vis = [0] * len(graph)

        def dfs(pos, color):
            vis[pos] = color
            for i in graph[pos]:
                # 顔色相同 or （未通路 且 繼續深搜為False）
                # 可直接傳回False
                if vis[i] == color or not (vis[i] or dfs(i, -color)):
                    return False
            return True

        # 不一定為聯通圖，需周遊每一個節點
        for i in range(len(graph)):
            if not vis[i] and not dfs(i, 1):
                return False
        return True


# 作者：GiaoGiaoWo
# 連結：https://leetcode-cn.com/problems/is-graph-bipartite/solution/python3-dfs-ji-jian-dai-ma-shi-jian-88kong-jian-10/
# 來源：力扣（LeetCode）
# 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
###########
           

BFS 的核心就是隊列

首先進入for 循環，加一個節點進來，染色。尋找與其相接的點是否染色，如果染色一樣，

傳回False。顔色不一樣，繼續看其他相鄰點。遇到沒有染色的節點，此時染不同色，同時加入清單中，因為染色後就要找它相鄰節點。

1.for 循環， 看目前節點是否已經染色，如果染色就看下一節點，否則就預設染成紅色（大多數的節點在while queue中就已經被染色）

2.for循環，對目前已經才染色過，并且加入隊列的點，清單循環，每次從清單彈出一個節點，看和其相鄰的節點是否染色，

如果已經染色并且顔色相同，直接傳回False;
 如果染色，但是顔色不同，什麼也不做，看其他相鄰點
 如果還未染色，這次染成不一樣的顔色，加入隊列，看是否可分
           

3.循環結束都沒有False,那麼說明可分，傳回True

注意：

這裡沒有用雙向隊列，因為可以不考慮順序，每個節點的相鄰節點都會被判斷，不用考慮順序

#**********      本題還可以使用BFS來做      *************#
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        record = [0] * n
        UNCOLORED, RED, BLUE = 0, 1, -1#設定三種顔色

        for i in range(n):
            if record[i] != UNCOLORED:
                continue

            record[i] = RED#如果沒有填色，則預設填紅色
            queue = [i]#将染色後的序号加入清單
            while queue:
                node = queue.pop()#彈出目前已染色的節點索引
                for block in graph[node]:#和已染色的點相鄰的快
                    if record[block] == UNCOLORED:#m沒有染色，染成不同的顔色
                        record[block] = BLUE if record[node] == RED else RED
                        queue.append(block)
                    elif record[block] == record[node]:#如果顔色相同，傳回False
                        return False
        return True
            

#******************************************************#
if __name__ == "__main__":
    s = Solution()
    graph = [[1,3], [0,2], [1,3], [0,2]]
    graph = [[1,2,3], [0,2], [0,1,3], [0,2]]
    print(s.isBipartite(graph))