golang中怎么利用leetcode 判斷二分圖

golang中怎么利用leetcode 判斷二分圖，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

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

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

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

示例 1:

輸入: [[1,3], [0,2], [1,3], [0,2]]輸出: true解釋: 無向圖如下:0----1|    ||    |3----2我們可以將節(jié)點分成兩組: {0, 2} 和 {1, 3}。

示例 2:

輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]輸出: false解釋: 無向圖如下:0----1| \  ||  \ |3----2

我們不能將節(jié)點分割成兩個獨立的子集。

注意:

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

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

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

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

解題思路

深度優(yōu)先搜索著色

1，如果節(jié)點屬于第一個集合，將其著為藍色，否則著為紅色。

2，只有在二分圖的情況下，可以使用貪心思想給圖著色：一個節(jié)點為藍色，說明它的所有鄰接點為紅色，它的鄰接點的所有鄰接點為藍色，依此類推。

3，使用數(shù)組（或者哈希表）記錄每個節(jié)點的顏色： color[node]。顏色可以是 1，2，或者未著色（0）。

4，搜索節(jié)點時，需要考慮圖是非連通的情況。

5，對每個未著色節(jié)點，從該節(jié)點開始深度優(yōu)先搜索著色。每個鄰接點都可以通過當前節(jié)點著相反的顏色。

6，如果存在當前點和鄰接點顏色相同，則著色失敗。

7，使用棧完成深度優(yōu)先搜索，棧類似于節(jié)點的 “todo list”，存儲著下一個要訪問節(jié)點的順序。在 graph[node] 中，對每個未著色鄰接點，著色該節(jié)點并將其放入到棧中。

代碼實現(xiàn)

func isBipartite(graph [][]int) bool {    l:=len(graph)
    if l<2{return true    }    color:=make([]int,l)    var q []int    for i:=0;i<l;i++{        if color[i]==0{           q=append(q,i)           for len(q)>0{               if color[q[0]]==0{                  color[q[0]]=1                }               for _,j:=range(graph[q[0]]){                   if  color[j]==0{                       q=append(q,j)                       if color[q[0]]==1{                           color[j]=2                       }else if color[q[0]]==2{                           color[j]=1                       }                   }else if color[q[0]]==color[j]{                       return false                   }               }               q=q[1:]           }        }    }        return true}

關于golang中怎么利用leetcode 判斷二分圖問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。