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

創(chuàng)新互聯(lián)建站主營(yíng)張家界網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都App定制開(kāi)發(fā),張家界h5重慶小程序開(kāi)發(fā)搭建,張家界網(wǎng)站營(yíng)銷推廣歡迎張家界等地區(qū)企業(yè)咨詢

給定一個(gè)無(wú)向圖graph，當(dāng)這個(gè)圖為二分圖時(shí)返回true。

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

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

示例 1:

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

示例 2:

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

我們不能將節(jié)點(diǎn)分割成兩個(gè)獨(dú)立的子集。

注意:

graph 的長(zhǎng)度范圍為 [1, 100]。

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

graph[i] 不會(huì)包含 i 或者有重復(fù)的值。

圖是無(wú)向的: 如果j 在 graph[i]里邊, 那么 i 也會(huì)在 graph[j]里邊。

解題思路

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

1，如果節(jié)點(diǎn)屬于第一個(gè)集合，將其著為藍(lán)色，否則著為紅色。

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

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

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

5，對(duì)每個(gè)未著色節(jié)點(diǎn)，從該節(jié)點(diǎn)開(kāi)始深度優(yōu)先搜索著色。每個(gè)鄰接點(diǎn)都可以通過(guò)當(dāng)前節(jié)點(diǎn)著相反的顏色。

6，如果存在當(dāng)前點(diǎn)和鄰接點(diǎn)顏色相同，則著色失敗。

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

代碼實(shí)現(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}

關(guān)于golang中怎么利用leetcode 判斷二分圖問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

文章名稱：golang中怎么利用leetcode判斷二分圖
網(wǎng)站網(wǎng)址：http://aaarwkj.com/article10/pesggo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、定制開(kāi)發(fā)、響應(yīng)式網(wǎng)站、軟件開(kāi)發(fā)、全網(wǎng)營(yíng)銷推廣、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)