溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
golang中怎么利用leetcode 判斷二分圖，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
給定一個無向圖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]里邊。
解題思路
深度優先搜索著色
1，如果節點屬于第一個集合，將其著為藍色，否則著為紅色。
2，只有在二分圖的情況下，可以使用貪心思想給圖著色：一個節點為藍色，說明它的所有鄰接點為紅色，它的鄰接點的所有鄰接點為藍色，依此類推。
3，使用數組（或者哈希表）記錄每個節點的顏色： color[node]。顏色可以是 1，2，或者未著色（0）。
4，搜索節點時，需要考慮圖是非連通的情況。
5，對每個未著色節點，從該節點開始深度優先搜索著色。每個鄰接點都可以通過當前節點著相反的顏色。
6，如果存在當前點和鄰接點顏色相同，則著色失敗。
7，使用棧完成深度優先搜索，棧類似于節點的 “todo list”，存儲著下一個要訪問節點的順序。在 graph[node] 中，對每個未著色鄰接點，著色該節點并將其放入到棧中。
代碼實現
func isBipartite(graph [][]int) bool {l:=len(graph)if l<2{return true}color:=make([]int,l)var q []intfor 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 判斷二分圖問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
