使用DFS检查图是否为二分图的Golang程序

深度优先搜索（DFS）算法是一种经典算法，用于遍历和搜索图。本文将学习如何开发Golang程序，在其中使用DFS检查图是否为二分图。我们将使用两种不同的方法来实现此结果。

语法

func len(v Type) int

len()函数用于获取任何参数的长度。它接受一个数据类型变量作为参数，该变量的长度将被查找，并返回表示变量长度的整数值。

算法

• 首先，我们需要导入fmt包。然后创建一个名为isBipare的函数。在函数内部，初始化一个名为visited的大小为n的布尔数组来跟踪访问的顶点，并初始化一个名为colors的大小为n的整数数组来存储顶点的颜色。

• 接下来，创建一个名为DFS的函数来遍历图。该函数接受两个参数，即当前节点和该节点的颜色。

• 在该函数中，遍历当前节点的所有邻居。如果邻居未被访问，则使用邻居作为当前节点和相反颜色（1-color）作为输入颜色递归调用DFS函数。

• 如果递归调用返回false，则图不是二分图，因此返回false。

• 遍历图中的所有未访问顶点。对于每个未访问的顶点，使用该顶点作为当前节点和颜色0或1调用DFS函数。

• 现在，开始main()函数。在该函数中，初始化图的顶点并在屏幕上打印它们。

• 通过将图作为参数传递给函数来调用isBipartite()函数，并将结果存储在变量中。

• 使用fmt.Println()在屏幕上打印获得的变量中的结果。

示例1

在此示例中，我们将编写一个Go语言程序，通过使用二分法方法来检查图是否为二分图。在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("给定的图顶点为：", graph1)
   var result bool = isBipartite(graph1)
   if result {
      fmt.Println("给定的图是二分图")
  } else {
      fmt.Println("给定的图不是二分图")
   }
   fmt.Println()
   graph2 := [][]int{{1, 2, 3}, {0, 2}, {1, 3}, {0, 2}}
   fmt.Println("给定的图顶点为：", graph2)
   result = isBipartite(graph2)
   if result {
      fmt.Println("给定的图是二分图")
   } else {
      fmt.Println("给定的图不是二分图")
   }
}

输出

给定的图顶点为： [[1 3] [0 2] [1 3] [0 2]]
给定的图是二分图

给定的图顶点为： [[1 2 3] [0 2] [1 3] [0 2]]
给定的图不是二分图

例子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("给定的图形顶点是:", graph1)
    var result bool = isBipartite(graph1)
    if result {
        fmt.Println("给定的图形是二分图")
    } else {
        fmt.Println("给定的图形不是二分图")
    }
    fmt.Println()
    graph2 := [][]int {{1, 2, 3}, {0, 2}, {1, 3}, {0, 2}}
    fmt.Println("给定的图形顶点是:", graph2)
    result = isBipartite(graph2)
    if result {
        fmt.Println("给定的图形是二分图")
    } else {
        fmt.Println("给定的图形不是二分图")
    }
}

输出

给定的图形顶点是: [[1 3] [0 2] [1 3] [0 2]]
给定的图形是二分图

给定的图形顶点是: [[1 2 3] [0 2] [1 3] [0 2]]
给定的图形不是二分图

结论

我们已成功编译和执行了一个Go语言程序，用于检查图形是否为二分图，并给出了Examples。 在第一个例子中，我们使用了2着色法，而在第二个程序中，我们使用了布尔着色方法来实现结果。