数据结构
网络
关系数据库管理系统
操作系统
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 次查看
