数据结构
图(graph)

图

图(graph)是一种非线性数据结构，由顶点(vertex)和(边 edge)组成。

  • 顶点（vertex）：图中的元素；
  • 边（edge）：图中的顶点与其他任意顶点建立连接的关系；
  • 顶点的度（degree)：跟顶点相连接的边的条数。
  • 入度（In-degree）和出度（Out-degree）：对于有向图，一个顶点的入度是指以其为终点的边数；出度指以该顶点为起点的边数；
  • 图有多种类型，包括有向图、无向图、简单图、多重图、有向图、无向图等；

图

图的表示

图的常用表示方式包括“邻接矩阵”和“邻接表”。

邻接矩阵

邻接矩阵（Adjacency Matrix）是图的常用存储表示。它使用一个 nxn 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

它的底层依赖一个二维数组。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

邻接矩阵具有以下特性。

  • 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
  • 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
  • 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为 O(n^2) ，内存占用较多。

以下是基于邻接矩阵表示图的实现代码：

/* 基于邻接矩阵实现的无向图类 */
type graphAdjMat struct {
    // 顶点列表，元素代表“顶点值”，索引代表“顶点索引”
    vertices []int
    // 邻接矩阵，行列索引对应“顶点索引”
    adjMat [][]int
}
 
/* 构造函数 */
func newGraphAdjMat(vertices []int, edges [][]int) *graphAdjMat {
    // 添加顶点
    n := len(vertices)
    adjMat := make([][]int, n)
    for i := range adjMat {
        adjMat[i] = make([]int, n)
    }
    // 初始化图
    g := &graphAdjMat{
        vertices: vertices,
        adjMat:   adjMat,
    }
    // 添加边
    // 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
    for i := range edges {
        g.addEdge(edges[i][0], edges[i][1])
    }
    return g
}
 
/* 获取顶点数量 */
func (g *graphAdjMat) size() int {
    return len(g.vertices)
}
 
/* 添加顶点 */
func (g *graphAdjMat) addVertex(val int) {
    n := g.size()
    // 向顶点列表中添加新顶点的值
    g.vertices = append(g.vertices, val)
    // 在邻接矩阵中添加一行
    newRow := make([]int, n)
    g.adjMat = append(g.adjMat, newRow)
    // 在邻接矩阵中添加一列
    for i := range g.adjMat {
        g.adjMat[i] = append(g.adjMat[i], 0)
    }
}
 
/* 删除顶点 */
func (g *graphAdjMat) removeVertex(index int) {
    if index >= g.size() {
        return
    }
    // 在顶点列表中移除索引 index 的顶点
    g.vertices = append(g.vertices[:index], g.vertices[index+1:]...)
    // 在邻接矩阵中删除索引 index 的行
    g.adjMat = append(g.adjMat[:index], g.adjMat[index+1:]...)
    // 在邻接矩阵中删除索引 index 的列
    for i := range g.adjMat {
        g.adjMat[i] = append(g.adjMat[i][:index], g.adjMat[i][index+1:]...)
    }
}
 
/* 添加边 */
// 参数 i, j 对应 vertices 元素索引
func (g *graphAdjMat) addEdge(i, j int) {
    // 索引越界与相等处理
    if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
        fmt.Errorf("%s", "Index Out Of Bounds Exception")
    }
    // 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)
    g.adjMat[i][j] = 1
    g.adjMat[j][i] = 1
}
 
/* 删除边 */
// 参数 i, j 对应 vertices 元素索引
func (g *graphAdjMat) removeEdge(i, j int) {
    // 索引越界与相等处理
    if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
        fmt.Errorf("%s", "Index Out Of Bounds Exception")
    }
    g.adjMat[i][j] = 0
    g.adjMat[j][i] = 0
}
 
/* 打印邻接矩阵 */
func (g *graphAdjMat) print() {
    fmt.Printf("\t顶点列表 = %v\n", g.vertices)
    fmt.Printf("\t邻接矩阵 = \n")
    for i := range g.adjMat {
        fmt.Printf("\t\t\t%v\n", g.adjMat[i])
    }
}

邻接表

(邻接表 adjacency list)使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。

邻接表仅存储实际存在的边，而边的总数通常远小于 n^2，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 O(n) 优化至 O(logn)；还可以把链表转换为哈希表，从而将时间复杂度降至 O(1)。

以下是基于邻接表表示图的实现代码：

/* 基于邻接表实现的无向图类 */
type graphAdjList struct {
    // 邻接表，key：顶点，value：该顶点的所有邻接顶点
    adjList map[Vertex][]Vertex
}
 
/* 构造函数 */
func newGraphAdjList(edges [][]Vertex) *graphAdjList {
    g := &graphAdjList{
        adjList: make(map[Vertex][]Vertex),
    }
    // 添加所有顶点和边
    for _, edge := range edges {
        g.addVertex(edge[0])
        g.addVertex(edge[1])
        g.addEdge(edge[0], edge[1])
    }
    return g
}
 
/* 获取顶点数量 */
func (g *graphAdjList) size() int {
    return len(g.adjList)
}
 
/* 添加边 */
func (g *graphAdjList) addEdge(vet1 Vertex, vet2 Vertex) {
    _, ok1 := g.adjList[vet1]
    _, ok2 := g.adjList[vet2]
    if !ok1 || !ok2 || vet1 == vet2 {
        panic("error")
    }
    // 添加边 vet1 - vet2, 添加匿名 struct{},
    g.adjList[vet1] = append(g.adjList[vet1], vet2)
    g.adjList[vet2] = append(g.adjList[vet2], vet1)
}
 
/* 删除边 */
func (g *graphAdjList) removeEdge(vet1 Vertex, vet2 Vertex) {
    _, ok1 := g.adjList[vet1]
    _, ok2 := g.adjList[vet2]
    if !ok1 || !ok2 || vet1 == vet2 {
        panic("error")
    }
    // 删除边 vet1 - vet2
    g.adjList[vet1] = DeleteSliceElms(g.adjList[vet1], vet2)
    g.adjList[vet2] = DeleteSliceElms(g.adjList[vet2], vet1)
}
 
/* 添加顶点 */
func (g *graphAdjList) addVertex(vet Vertex) {
    _, ok := g.adjList[vet]
    if ok {
        return
    }
    // 在邻接表中添加一个新链表
    g.adjList[vet] = make([]Vertex, 0)
}
 
/* 删除顶点 */
func (g *graphAdjList) removeVertex(vet Vertex) {
    _, ok := g.adjList[vet]
    if !ok {
        panic("error")
    }
    // 在邻接表中删除顶点 vet 对应的链表
    delete(g.adjList, vet)
    // 遍历其他顶点的链表，删除所有包含 vet 的边
    for v, list := range g.adjList {
        g.adjList[v] = DeleteSliceElms(list, vet)
    }
}
 
/* 打印邻接表 */
func (g *graphAdjList) print() {
    var builder strings.Builder
    fmt.Printf("邻接表 = \n")
    for k, v := range g.adjList {
        builder.WriteString("\t\t" + strconv.Itoa(k.Val) + ": ")
        for _, vet := range v {
            builder.WriteString(strconv.Itoa(vet.Val) + " ")
        }
        fmt.Println(builder.String())
        builder.Reset()
    }
}

图的遍历

树代表的是“一对多”的关系，而图则具有更高的自由度，可以表示任意的“多对多”关系。因此，我们可以把树看作图的一种特例。显然，树的遍历操作也是图的遍历操作的一种特例。

图和树都需要应用搜索算法来实现遍历操作。图的遍历方式也可分为两种：广度优先遍历和深度优先遍历。

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。

BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。

为了防止重复遍历顶点，我们需要借助一个哈希表 visited 来记录哪些节点已被访问。

/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
func graphBFS(g *graphAdjList, startVet Vertex) []Vertex {
    // 顶点遍历序列
    res := make([]Vertex, 0)
    // 哈希表，用于记录已被访问过的顶点
    visited := make(map[Vertex]struct{})
    visited[startVet] = struct{}{}
    // 队列用于实现 BFS, 使用切片模拟队列
    queue := make([]Vertex, 0)
    queue = append(queue, startVet)
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    for len(queue) > 0 {
        // 队首顶点出队
        vet := queue[0]
        queue = queue[1:]
        // 记录访问顶点
        res = append(res, vet)
        // 遍历该顶点的所有邻接顶点
        for _, adjVet := range g.adjList[vet] {
            _, isExist := visited[adjVet]
            // 只入队未访问的顶点
            if !isExist {
                queue = append(queue, adjVet)
                visited[adjVet] = struct{}{}
            }
        }
    }
    // 返回顶点遍历序列
    return res
}

深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。

这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似，在深度优先遍历中，我们也需要借助一个哈希表 visited 来记录已被访问的顶点，以避免重复访问顶点。

/* 深度优先遍历辅助函数 */
func dfs(g *graphAdjList, visited map[Vertex]struct{}, res *[]Vertex, vet Vertex) {
    // append 操作会返回新的的引用，必须让原引用重新赋值为新slice的引用
    *res = append(*res, vet)
    visited[vet] = struct{}{}
    // 遍历该顶点的所有邻接顶点
    for _, adjVet := range g.adjList[vet] {
        _, isExist := visited[adjVet]
        // 递归访问邻接顶点
        if !isExist {
            dfs(g, visited, res, adjVet)
        }
    }
}
 
/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
func graphDFS(g *graphAdjList, startVet Vertex) []Vertex {
    // 顶点遍历序列
    res := make([]Vertex, 0)
    // 哈希表，用于记录已被访问过的顶点
    visited := make(map[Vertex]struct{})
    dfs(g, visited, &res, startVet)
    // 返回顶点遍历序列
    return res
}
堆(heap)