資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用DFS檢查圖是否為二分圖的Go語言程式
深度優先搜尋（DFS）演算法是一種經典的用於遍歷和搜尋圖的演算法。在本文中，我們將學習如何開發一個Go語言程式，使用DFS檢查圖是否為二分圖。這裡我們將使用兩種不同的方法來實現結果。
語法
func len(v Type) int
len() 函式用於獲取任何引數的長度。它接受一個引數作為我們要查詢長度的資料型別變數，並返回一個整數值，即變數的長度。
演算法
首先，我們需要匯入fmt包。然後建立一個isBipare()函式。在函式內部，初始化一個大小為n的布林陣列visited來跟蹤已訪問的頂點，以及一個大小為n的整數陣列colors來儲存頂點的顏色。
接下來，建立一個DFS函式來遍歷圖。此函式接受兩個引數，即當前節點和該節點的顏色。
在此函式中，遍歷當前節點的所有鄰居。如果一個鄰居未被訪問，則遞迴呼叫DFS函式，將鄰居作為當前節點，並將相反的顏色（1-color）作為輸入顏色。
如果遞迴呼叫返回false，則圖不是二分圖，因此返回false。
遍歷圖中所有未訪問的頂點。對於每個未訪問的頂點，使用該頂點作為當前節點和顏色0或1呼叫DFS函式。
現在，開始main()函式。在此函式內部，初始化圖的頂點並在螢幕上列印它們。
接下來，透過將圖作為引數傳遞給函式來呼叫isBipartite()函式，並將結果儲存在一個變數中。
使用fmt.Println()在螢幕上列印變數中獲得的結果。
示例1
在此示例中，我們將編寫一個Go語言程式，使用2色著色方法來檢查圖是否為二分圖。在2色著色方法中，我們將兩種顏色分配給圖的頂點，然後我們使用DFS遍歷圖，併為每個頂點分配與其父頂點相反的顏色。
package main
import "fmt"
func isBipartite(graph [][]int) bool {
n := len(graph)
colors := make([]int, n)
visited := make([]bool, n)
var dfs func(int, int) bool
dfs = func(node int, color int) bool {
visited[node] = true
colors[node] = color
for _, neighbor := range graph[node] {
if !visited[neighbor] {
if !dfs(neighbor, 1-color) {
return false
}
} else if colors[neighbor] == colors[node] {
return false
}
}
return true
}
for i := 0; i < n; i++ {
if !visited[i] {
if !dfs(i, 0) {
return false
}
}
}
return true
}
func main() {
graph1 := [][]int{{1, 3}, {0, 2}, {1, 3}, {0, 2}}
fmt.Println("The given graph vertices are:", graph1)
var result bool = isBipartite(graph1)
if result {
fmt.Println("The given graph is bipartite")
} else {
fmt.Println("The given graph is not bipartite")
}
fmt.Println()
graph2 := [][]int{{1, 2, 3}, {0, 2}, {1, 3}, {0, 2}}
fmt.Println("The given graph vertices are:", graph2)
result = isBipartite(graph2)
if result {
fmt.Println("The given graph is bipartite")
} else {
fmt.Println("The given graph is not bipartite")
}
}
輸出
The given graph vertices are: [[1 3] [0 2] [1 3] [0 2]] The given graph is bipartite The given graph vertices are: [[1 2 3] [0 2] [1 3] [0 2]] The given graph is not bipartite
示例2
在此方法中，我們不使用兩種顏色，而是為每個頂點分配一個布林值，以指示它屬於二分圖的一部分還是另一部分。
package main
import "fmt"
func isBipartite(graph [][]int) bool {
n := len(graph)
colors := make([]int, n)
for i := range colors {
colors[i] = -1
}
for i := 0; i < n; i++ {
if colors[i] == -1 {
if !colorGraph(graph, colors, i, 0) {
return false
}
}
}
return true
}
func colorGraph(graph [][]int, colors []int, curr int, color int) bool {
colors[curr] = color
for _, neighbor := range graph[curr] {
if colors[neighbor] == -1 {
if !colorGraph(graph, colors, neighbor, 1-color) {
return false
}
} else if colors[neighbor] == color {
return false
}
}
return true
}
func main() {
graph1 := [][]int{{1, 3}, {0, 2}, {1, 3}, {0, 2}}
fmt.Println("The given graph vertices are:", graph1)
var result bool = isBipartite(graph1)
if result {
fmt.Println("The given graph is bipartite")
} else {
fmt.Println("The given graph is not bipartite")
}
fmt.Println()
graph2 := [][]int{{1, 2, 3}, {0, 2}, {1, 3}, {0, 2}}
fmt.Println("The given graph vertices are:", graph2)
result = isBipartite(graph2)
if result {
fmt.Println("The given graph is bipartite")
} else {
fmt.Println("The given graph is not bipartite")
}
}
輸出
The given graph vertices are: [[1 3] [0 2] [1 3] [0 2]] The given graph is bipartite The given graph vertices are: [[1 2 3] [0 2] [1 3] [0 2]] The given graph is not bipartite
結論
我們已經成功編譯並執行了一個Go語言程式來檢查圖是否為二分圖，並附帶了示例。這裡我們使用了兩個示例。在第一個示例中，我們使用2色著色方法，而在第二個程式中，我們使用布林著色方法來實現結果。
158 次檢視
