Golang 使用DFS检查图是否是二分图

深度优先搜索（DFS）算法是一种经典的用于遍历和搜索图的算法。本文将介绍如何开发使用Golang编写的程序，通过DFS算法来检查图是否是二分图。这里我们将使用两种不同的方法来实现结果。

语法

func len(v Type) int

len()函数用于获取任何参数的长度。它需要一个参数作为数据类型变量，我们希望找到它的长度，并返回整数值作为变量的长度。

步骤

首先，我们需要导入 fmt 包，然后创建一个名为 isBipare() 的函数。在函数内部，初始化一个布尔数组 visited，用来跟踪访问过的顶点，以及一个大小为 n 的整数数组 colors，用来存储顶点的颜色。
接下来创建一个 DFS 函数来遍历图。该函数接受两个参数，即当前节点和该节点的颜色。
在此函数中遍历当前节点的所有邻居。如果一个邻居没有被访问过，则使用邻居作为当前节点并使用相反的颜色（1-color）作为输入颜色来递归调用 DFS 函数。
如果递归调用返回 false，则图不是二分图，因此返回 false。
遍历图中所有未访问的顶点。对于每个未访问的顶点，使用该顶点作为当前节点并将颜色设为 0 或 1 来调用 DFS 函数。
现在开始主函数 main()。在该函数内，初始化一个图的顶点并将其打印在屏幕上。
通过将图作为参数传递给 isBipartite() 函数，并将结果存储在一个变量中，调用 isBipartite() 函数。
通过使用 fmt.Println() 将变量中的结果输出到屏幕上。

示例1

在此示例中，我们将编写一个 Go 语言程序，使用双色法来检查一个图是否是二分图。在双色法中，我们为图的顶点分配两种颜色，然后使用 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