图
图(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
}