图

图的表示

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

1. 邻接矩阵

设图的顶点数量为n，邻接矩阵使用一个n*n大小的矩阵来表示图，每一行（列）表示一个顶点，矩阵元素代表边，使用1或0表示两个顶点之间是否存在边。 邻接矩阵具有以下特性： - 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义 - 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。 - 将邻接矩阵的元素从1和0替换为权重，则可表示有权图

2. 邻接表

邻接表使用n个链表来表示图，链表节点表示顶点。第i个链表对应顶点i，其中存储了该顶点的所有邻接顶点。

图基础操作

图的基础操作可分为对“边”的操作和对“顶点”的操作。在“邻接矩阵”和“邻接表”两种表示方法下，实现方式有所不同。

基于邻接矩阵的实现

给定一个顶点数量为n的无向图，则各种操作的实现方式 - 添加或删除边：直接在矩阵中修改指定的边即可，使用\(O(1)\)的时间。而由于是无向图，因此需要同事更新两个方向的边。 - 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填0即可，使用\(O(n)\)时间 - 删除顶点：在邻接矩阵汇总删除一行一列。当删除首行首列时达到最差情况，需要将\((n-1)^2\)个元素“向左上移动”，从而需要\(O(n^2)\)时间 - 初始化：传入n个顶点，初始化长度为n的顶点列表vertices，使用\(O(n)\)时间；初始化\(n*n\)大小的邻接矩阵adjMat使用\(O(n^2)\)时间

type graphAdjMat struct {
    vertices []int
    adjMat   [][]int
}

func newGraphAdjMat(vertices []int, edges [][]int) *graphAdjMat {
    // Add vertices
    n := len(vertices)
    adjMat := make([][]int, n)
    for i := range adjMat {
        adjMat[i] = make([]int, n)
    }
    // 初始化图
    g := &graphAdjMat{vertices, adjMat}
    // 添加边
    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(v int) {
    n := g.size()
    // 向顶点列表中添加新顶点的值
    g.vertices = append(g.vertices, v)
    // 在邻接矩阵中添加一行
    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:]...)
    for i := g.adjMat {
        g.adjMat[i] = append(g.adjMat[i][:index], g.adjMat[i][index+1:]...)
    }
}

// 添加边
func(g *graphAdjMat) addEdge(v1, v2 int) {
    // 索引越界与相等处理
    if v1<0 || v2 <0 || v1 >=g.size() || v2 >=g.size() || v1 == v2 {
        return
    }
    // 在无向图中，邻接矩阵关于主对角线对称
    g.adjMat[v1][v2] = 1
    g.adjMat[v2][v1] = 1
}

// 删除边
func(g*graphAdjMat) removeEdge(v1, v2 int) {
    // 索引越界与相等处理
    if v1<0 || v2 <0 || v1 >=g.size() || v2 >=g.size() || v1 == v2 {
        return
    }
    // 在无向图中，邻接矩阵关于主对角线对称
    g.adjMat[v1][v2] = 0
    g.adjMat[v2][v1] = 0
}

// 打印邻接矩阵
func(g *graphAdjMat)print() {
    for i := range g.adjMat {
        fmt.Printf("\t\t\t%v\n", g.adjMat[i])
    }
}

基于邻接表的实现

设无向图的顶点总数为n，边总数为m - 添加边: 在顶点对应链表的末尾添加边即可，使用\(O(1)\)时间。因为是无向图，所以需要同时添加两个方向的边 - 删除边：在顶点对应链表中查找并删除指定边，使用\(O(m)\)时间。在无向图中，需要同事删除两个方向的边。 - 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用\(O(1)\)时间 - 删除顶点：需要遍历整个邻接表，删除包含指定顶点的所有边，使用\(O(n+m)\)时间 - 初始化：在邻接表中创建n个顶点和2m条边，使用\(O(n+m)\)时间

type Vertex int
type graphAdjList struct {
    adjList map[Vertex][]Vertex
}

func DeleteSliceElms(list []Vertex, vet Vertex) []Vertex {
    // 查找要删除的元素索引要删除的元素索引
    index := -1
    for i, v := range list {
        if v == vet {
            index = i
            break
        }
    }

    // 如果找到了元素，则从切片中删除它
    if index != -1 {
        list = append(list[:index], list[index+1:]...)
    }
    return list
}

func newGraghAdjList(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) addVertex(v Vertex) {
    _, ok := g.adjList[v]
    if ok {
        return
    }
    g.adjList[v] = make([]Vertex, 0)
}

// 删除顶点
func (g *graphAdjList) removeVertex(v Vertex) {
    _, ok := g.adjList[v]
    if !ok {
        return
    }
    // 删除所有指向v的边
    delete(g.adjList, v)
    for vet, list := range g.adjList {
        g.adjList[vet] = DeleteSliceElms(list, vet)
    }
}

// 添加边
func (g *graphAdjList) addEdge(v1, v2 Vertex) {
    g.adjList[v1] = append(g.adjList[v1], v2)
    g.adjList[v2] = append(g.adjList[v2], v1)
}

// 删除边
func (g *graphAdjList) removeEdge(v1, v2 Vertex) {
    _, ok1 := g.adjList[v1]
    _, ok2 := g.adjList[v2]
    if !ok1 || !ok2 || v1 == v2 {
        return
    }
    g.adjList[v1] = DeleteSliceElms(g.adjList[v1], v2)
    g.adjList[v2] = DeleteSliceElms(g.adjList[v2], v1)
}

图的遍历

树代表的是“一对多“的关系，而图则具有更高的自由度，可以表示任意的“多对多“关系。图和树都需要应用搜索算法来实现遍历操作。图的遍历方式也可分为两种：广度优先遍历和深度优先遍历

广度优先遍历