golang-cookbook

Appearance

intro ​

Go 语言（Golang）中图算法（Graph Algorithms）和大 O 算法（Big O Notation）是计算机科学中的两个重要主题。

1. Go 语言中的图算法（Graph Algorithms） ​

图是一种由节点（Vertex）和边（Edge）组成的结构。在图算法中，常见的操作包括图的遍历、最短路径算法、最小生成树等。Go 语言虽然没有内建的图数据结构，但你可以轻松地使用 Go 语言的内建数据结构来表示图，并实现常见的图算法。

1.1 图的表示方式 ​

在 Go 中，图的表示一般有以下几种方式：

  • 邻接矩阵（Adjacency Matrix）
  • 邻接表（Adjacency List）
邻接矩阵 ​

邻接矩阵是一个二维数组，如果有边从节点 i 到节点 j，则矩阵中 matrix[i][j] = 1，否则 matrix[i][j] = 0。

go
type Graph struct {
    vertices int
    adjMatrix [][]int
}

func NewGraph(vertices int) *Graph {
    adjMatrix := make([][]int, vertices)
    for i := range adjMatrix {
        adjMatrix[i] = make([]int, vertices)
    }
    return &Graph{vertices: vertices, adjMatrix: adjMatrix}
}

func (g *Graph) AddEdge(i, j int) {
    g.adjMatrix[i][j] = 1
    g.adjMatrix[j][i] = 1 // 如果是无向图
}
邻接表 ​

邻接表使用一个数组，其中每个元素是一个链表或切片，表示从该节点出发的边。

go
type Graph struct {
    adjList map[int][]int
}

func NewGraph() *Graph {
    return &Graph{adjList: make(map[int][]int)}
}

func (g *Graph) AddEdge(i, j int) {
    g.adjList[i] = append(g.adjList[i], j)
    g.adjList[j] = append(g.adjList[j], i) // 如果是无向图
}

1.2 常见的图算法 ​

  • 广度优先搜索（BFS, Breadth-First Search）：从某个起点开始，沿着图的宽度遍历图，先访问所有邻居节点。
go
func BFS(g *Graph, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    visited[start] = true
    result := []int{}
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)

        for _, neighbor := range g.adjList[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }

    return result
}
  • 深度优先搜索（DFS, Depth-First Search）：从某个起点开始，沿着图的深度遍历图，尽量深入每个节点直到无法继续。
go
func DFS(g *Graph, start int) []int {
    visited := make(map[int]bool)
    var result []int

    var dfsHelper func(int)
    dfsHelper = func(node int) {
        visited[node] = true
        result = append(result, node)

        for _, neighbor := range g.adjList[node] {
            if !visited[neighbor] {
                dfsHelper(neighbor)
            }
        }
    }

    dfsHelper(start)
    return result
}
  • Dijkstra 最短路径算法（Dijkstra’s Shortest Path Algorithm）：用于找到从起点到所有其他节点的最短路径。
go
import "math"

func Dijkstra(g *Graph, start int) map[int]int {
    distances := make(map[int]int)
    for vertex := range g.adjList {
        distances[vertex] = math.MaxInt
    }
    distances[start] = 0
    
    visited := make(map[int]bool)
    
    for len(visited) < len(g.adjList) {
        minVertex := -1
        minDistance := math.MaxInt
        for vertex, distance := range distances {
            if !visited[vertex] && distance < minDistance {
                minDistance = distance
                minVertex = vertex
            }
        }

        if minVertex == -1 {
            break
        }
        
        visited[minVertex] = true
        for _, neighbor := range g.adjList[minVertex] {
            newDist := minDistance + 1 // 假设所有边的权重为 1
            if newDist < distances[neighbor] {
                distances[neighbor] = newDist
            }
        }
    }
    
    return distances
}

2. 大O算法（Big O Notation） ​

大 O 符号用于描述算法的时间复杂度和空间复杂度，衡量算法在输入规模增加时的性能。以下是一些常见的大 O 复杂度及其解释：

  • O(1)：常数时间复杂度，表示无论输入规模多大，算法所需的时间始终是常数。

  • O(log n)：对数时间复杂度，表示输入规模增加时，所需的时间增长速度是对数级别的（例如，二分查找）。

  • O(n)：线性时间复杂度，表示输入规模与所需时间成正比。

  • O(n log n)：线性对数时间复杂度，常见于高效的排序算法，如归并排序、快速排序。

  • O(n²)：平方时间复杂度，表示时间增长速度是输入规模的平方，常见于简单排序算法，如冒泡排序、插入排序。

  • O(2^n)：指数时间复杂度，表示时间随着输入规模的增加呈指数增长，通常出现在递归算法中。

  • O(n!)：阶乘时间复杂度，表示时间随着输入规模的增加呈阶乘增长，通常出现在解决排列问题时。

3. Go 中图算法的大 O 分析 ​

  • BFS 和 DFS 时间复杂度：O(V + E)，其中 V 是图的节点数，E 是图的边数。因为每个节点和每条边都只会被访问一次。

  • Dijkstra 时间复杂度：O((V + E) log V)，使用优先队列来优化搜索。

  • Kruskal 和 Prim 最小生成树算法：

    • Kruskal 算法：O(E log E)，因为需要排序边。
    • Prim 算法：O((V + E) log V)，使用优先队列来优化最小边的选择。

总结 ​

  • 图算法：在 Go 中，图算法通常通过邻接表或邻接矩阵来实现，广泛用于图遍历、最短路径和最小生成树等问题。
  • 大 O 复杂度：对于不同的算法，大 O 符号帮助我们了解它们在面对不同规模输入时的时间和空间表现。