• 小白备战大厂算法笔试(七)——图

    图

    图是一种非线性数据结构，由顶点和边组成。我们可以将图 (G) 抽象地表示为一组顶点 (V) 和一组边 (E) 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图。

    V = { 1, 2, 3, 4, 5 } &E = { (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5) } &G ={ V, E }

    如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作是一种从链表拓展而来的数据结构。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，从而更为复杂。

    image-20230912145001860

    基础知识

    根据边是否具有方向，可分为无向图和有向图。

    • 在无向图中，边表示两顶点之间的“双向”连接关系，例如微信或 QQ 中的“好友关系”。
    • 在有向图中，边具有方向性，两个方向的边是相互独立的，例如微博或抖音上的“关注”与“被关注”关系。

    image-20230912145312880

    根据所有顶点是否连通，可分为连通图和非连通图。

    • 对于连通图，从某个顶点出发，可以到达其余任意顶点。
    • 对于非连通图，从某个顶点出发，至少有一个顶点无法到达。

    image-20230912145454503

    可以为边添加“权重”变量，从而得到有权图。例如在王者荣耀等手游中，系统会根据共同游戏时间来计算玩家之间的“亲密度”，这种亲密度网络就可以用有权图来表示。

    image-20230912145751701

    图数据结构包含以下常用术语。

    • 邻接：当两顶点之间存在边相连时，称这两顶点“邻接”。在上图中，顶点 1 的邻接顶点为顶点 2、3、5。
    • 路径：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在上图中，边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。
    • 度：一个顶点拥有的边数。对于有向图，入度表示有多少条边指向该顶点，出度表示有多少条边从该顶点指出。

    相关表示

    图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

    邻接矩阵

    设图的顶点数量为 (n) ，邻接矩阵使用一个 (n * n) 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 (1) 或 (0) 表示两个顶点之间是否存在边。

    设邻接矩阵为 (M)、顶点列表为 (V) ，那么矩阵元素 (M[i, j] = 1) 表示顶点 (V[i]) 到顶点 (V[j]) 之间存在边，反之 (M[i, j] = 0) 表示两顶点之间无边。

    image-20230912150255375

    邻接矩阵具有以下特性。

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

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

    邻接表

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

    image-20230912150454543

    邻接表仅存储实际存在的边，而边的总数通常远小于 (n^2) ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 (O(n)) 优化至 (O(log n)) ；还可以把链表转换为哈希表，从而将时间复杂度降低至 (O(1)) 。

    常见应用

    许多现实系统都可以用图来建模，相应的问题也可以约化为图计算问题。

    顶点边图计算问题
    社交网络用户好友关系潜在好友推荐
    地铁线路站点站点间的连通性最短路线推荐
    太阳系星体星体间的万有引力作用行星轨道计算

    基础操作

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

    邻接矩阵

    给定一个顶点数量为 (n) 的无向图：

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

    image-20230912151414493

    image-20230912151426183

    image-20230912151439459

    image-20230912151502200

    image-20230912151511136

    Python：

    class GraphAdjMat:
    """基于邻接矩阵实现的无向图类"""

    # 顶点列表，元素代表“顶点值”，索引代表“顶点索引”
    vertices: list[int] = []
    # 邻接矩阵，行列索引对应“顶点索引”
    adj_mat: list[list[int]] = []

    def __init__(self, vertices: list[int], edges: list[list[int]]):
        """构造方法"""
        self.vertices: list[int] = []
        self.adj_mat: list[list[int]] = []
        # 添加顶点
        for val in vertices:
            self.add_vertex(val)
        # 添加边
        # 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
        for e in edges:
            self.add_edge(e[0], e[1])

    def size(self) -> int:
        """获取顶点数量"""
        return len(self.vertices)

    def add_vertex(self, val: int):
        """添加顶点"""
        n = self.size()
        # 向顶点列表中添加新顶点的值
        self.vertices.append(val)
        # 在邻接矩阵中添加一行
        new_row = [0] * n
        self.adj_mat.append(new_row)
        # 在邻接矩阵中添加一列
        for row in self.adj_mat:
            row.append(0)

    def remove_vertex(self, index: int):
        """删除顶点"""
        if index >= self.size():
            raise IndexError()
        # 在顶点列表中移除索引 index 的顶点
        self.vertices.pop(index)
        # 在邻接矩阵中删除索引 index 的行
        self.adj_mat.pop(index)
        # 在邻接矩阵中删除索引 index 的列
        for row in self.adj_mat:
            row.pop(index)

    def add_edge(self, i: int, j: int):
        """添加边"""
        # 参数 i, j 对应 vertices 元素索引
        # 索引越界与相等处理
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        # 在无向图中，邻接矩阵沿主对角线对称，即满足 (i, j) == (j, i)
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1

    def remove_edge(self, i: int, j: int):
        """删除边"""
        # 参数 i, j 对应 vertices 元素索引
        # 索引越界与相等处理
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0

    def print(self):
        """打印邻接矩阵"""
        print("顶点列表 =", self.vertices)
        print("邻接矩阵 =")
        print_matrix(self.adj_mat)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    Go：

    /* 基于邻接矩阵实现的无向图类 */
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])
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    邻接表

    设无向图的顶点总数为 (n)、边总数为 (m) ：

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

    image-20230912155820813

    image-20230912155836762

    image-20230912155848211

    image-20230912155900290

    image-20230912155914614

    在邻接表中使用 Vertex 节点类来表示顶点：

    1. 如果选择通过顶点值来区分不同顶点，那么值重复的顶点将无法被区分。
    2. 如果类似邻接矩阵那样，使用顶点列表索引来区分不同顶点。那么，假设想要删除索引为 (i) 的顶点，则需要遍历整个邻接表，将其中 (> i) 的索引全部减 (1) ，这样操作效率较低。
    3. 因此考虑引入顶点类 Vertex ，使得每个顶点都是唯一的对象，此时删除顶点时就无须改动其余顶点了。

    Python：

    class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        # 邻接表，key: 顶点，value：该顶点的所有邻接顶点
        self.adj_list = dict[Vertex, Vertex]()
        # 添加所有顶点和边
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def size(self) -> int:
        """获取顶点数量"""
        return len(self.adj_list)

    def add_edge(self, vet1: Vertex, vet2: Vertex):
        """添加边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        # 添加边 vet1 - vet2
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def remove_edge(self, vet1: Vertex, vet2: Vertex):
        """删除边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        # 删除边 vet1 - vet2
        self.adj_list[vet1].remove(vet2)
        self.adj_list[vet2].remove(vet1)

    def add_vertex(self, vet: Vertex):
        """添加顶点"""
        if vet in self.adj_list:
            return
        # 在邻接表中添加一个新链表
        self.adj_list[vet] = []

    def remove_vertex(self, vet: Vertex):
        """删除顶点"""
        if vet not in self.adj_list:
            raise ValueError()
        # 在邻接表中删除顶点 vet 对应的链表
        self.adj_list.pop(vet)
        # 遍历其他顶点的链表，删除所有包含 vet 的边
        for vertex in self.adj_list:
            if vet in self.adj_list[vertex]:
                self.adj_list[vertex].remove(vet)

    def print(self):
        """打印邻接表"""
        print("邻接表 =")
        for vertex in self.adj_list:
            tmp = [v.val for v in self.adj_list[vertex]]
            print(f"{vertex.val}: {tmp},")

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    Go：

    /* 基于邻接表实现的无向图类 */
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()
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    效率对比

    设图中共有 (n) 个顶点和 (m) 条边，下表对比了邻接矩阵和邻接表的时间和空间效率。

    邻接矩阵邻接表（链表）邻接表（哈希表）
    判断是否邻接(O(1))(O(m))(O(1))
    添加边(O(1))(O(1))(O(1))
    删除边(O(1))(O(m))(O(1))
    添加顶点(O(n))(O(1))(O(1))
    删除顶点(O(n^2))(O(n + m))(O(n))
    内存空间占用(O(n^2))(O(n + m))(O(n + m))

    通过观察，似乎邻接表（哈希表）的时间与空间效率最优。但实际上，在邻接矩阵中操作边的效率更高，只需要一次数组访问或赋值操作即可。综合来看，邻接矩阵体现了“以空间换时间”的原则，而邻接表体现了“以时间换空间”的原则。

    遍历

    树代表的是“一对多”的关系，而图则具有更高的自由度，可以表示任意的“多对多”关系。因此，可以把树看作是图的一种特例。显然，树的遍历操作也是图的遍历操作的一种特例。图和树都都需要应用搜索算法来实现遍历操作。图的遍历方式可分为两种：广度优先遍历和深度优先遍历。它们也常被称为广度优先搜索和深度优先搜索，简称 BFS 和 DFS 。

    BFS

    广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。如下图所示，从左上角顶点出发，先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

    image-20230912174422761

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

    1. 将遍历起始顶点 startVet 加入队列，并开启循环。
    2. 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
    3. 循环步骤 2. ，直到所有顶点被访问完成后结束。

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

    Python：

    def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历 BFS"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希表，用于记录已被访问过的顶点
    visited = set[Vertex]([start_vet])
    # 队列用于实现 BFS
    que = deque[Vertex]([start_vet])
    # 以顶点 vet 为起点，循环直至访问完所有顶点
    while len(que) > 0:
        vet = que.popleft()  # 队首顶点出队
        res.append(vet)  # 记录访问顶点
        # 遍历该顶点的所有邻接顶点
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue  # 跳过已被访问过的顶点
            que.append(adj_vet)  # 只入队未访问的顶点
            visited.add(adj_vet)  # 标记该顶点已被访问
    # 返回顶点遍历序列
    return res

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    Go：

    /* 广度优先遍历 BFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
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
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    参考以下图示以加深理解：

    image-20230912174715099

    image-20230912174741690

    image-20230912174801580

    image-20230912174821569

    image-20230912174839431

    image-20230912174857770

    image-20230912174916397

    image-20230912174929464

    image-20230912174945179

    image-20230912175004665

    image-20230912175026229

    广度优先遍历的序列不唯一。广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序是允许被任意打乱的。

    时间复杂度： 所有顶点都会入队并出队一次，使用 (O(|V|)) 时间；在遍历邻接顶点的过程中，由于是无向图，因此所有边都会被访问 (2) 次，使用 (O(2|E|)) 时间；总体使用 (O(|V| + |E|)) 时间。

    空间复杂度： 列表 res ，哈希表 visited ，队列 que 中的顶点数量最多为 (|V|) ，使用 (O(|V|)) 空间。

    DFS

    深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如下图所示，从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。

    image-20230912180042138

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

    Python：

    def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历 DFS 辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问过的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)

def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历 DFS"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希表，用于记录已被访问过的顶点
    visited = set[Vertex]()
    dfs(graph, visited, res, start_vet)
    return res

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    Go：

    /* 深度优先遍历 DFS 辅助函数 */
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)
        }
    }
}

/* 深度优先遍历 DFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
func graphDFS(g *graphAdjList, startVet Vertex) []Vertex {
    // 顶点遍历序列
    res := make([]Vertex, 0)
    // 哈希表，用于记录已被访问过的顶点
    visited := make(map[Vertex]struct{})
    dfs(g, visited, &res, startVet)
    // 返回顶点遍历序列
    return res
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    参考以下图示以加深理解：

    image-20230912180235095

    image-20230912180245454

    image-20230912180256372

    image-20230912180307408

    image-20230912180318385

    image-20230912180333567

    image-20230912180356653

    image-20230912180405108

    image-20230912180417402

    image-20230912180428906

    image-20230912180445258

    • 直虚线代表向下递推，表示开启了一个新的递归方法来访问新顶点。
    • 曲虚线代表向上回溯，表示此递归方法已经返回，回溯到了开启此递归方法的位置。

    时间复杂度： 所有顶点都会被访问 (1) 次，使用 (O(|V|)) 时间；所有边都会被访问 (2) 次，使用 (O(2|E|)) 时间；总体使用 (O(|V| + |E|)) 时间。

    空间复杂度： 列表 res ，哈希表 visited 顶点数量最多为 (|V|) ，递归深度最大为 (|V|) ，因此使用 (O(|V|)) 空间。

    References：https://www.hello-algo.com/chapter_graph/

  • 相关阅读:
    混凝土和砖石设计：IES Quick Suite Crack
    iOS-系统弹窗调用，
    546、Zookeeper详细入门教程系列 -【Zookeeper内部原理】 2022.11.06
    java 基于 SpringMVC+Mybaties+ Html5 + Vue 前后端分离 房地产管理系统 的 设计与实现
    Python学习之CSDN21天学习挑战赛计划之1
    Flink Hive Catalog操作案例
    OpenAI：我们暂停了ChatGPT Plus新用户注册
    Docker Cgroups资源控制
    GAMES101-ASSIGNMENT8（作业8）
    解决六大痛点促进企业更好使用生成式AI，亚马逊云科技顾凡采访分享可用方案
  • 原文地址：https://blog.csdn.net/m0_63230155/article/details/132869546