图的表示

邻接表

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

# graph[x] 存储 x 的所有邻居节点以及对应的权重
graph: List[List[int, int]] 

另一种方法

h[],n[],ne[],idx

• 用h数组保存各个节点能到的第一个节点的编号.开始时,h[i]全部为-1
• 用e数组保存节点编号,ne数组保存e数组对应位置的下一个节点所在的索引
• 用idx保存下一个e数组中,可以放入节点位置的索引
• 插入边使用的头插法,例如插入:a -> b.首先把b节点存入e数组,e[idx]=b.然后b节点的后继是h[a],ne[idx]=h[a].最后,a的后继更新为b节点的编号,h[a] = idx,索引指向下一个可以存储节点的位置,idx++

邻接矩阵

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

# matrix[x][y] 记录 x 指向 y 的边的权重，0 表示不相邻
matrix: List[List[int]]

图的基本操作

基于邻接矩阵的实现

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

class GraphAdjMat:
    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)
        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()
        self.vertices.pop(index)
        self.adj_mat.pop(index)
        for row in self.adj_mat:
            row.pop(index)

    def add_edge(self, i:int, j:int):
        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)

基于邻接表的实现

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

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

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        # 邻接表，key：顶点，value：该顶点的所有邻接顶点
        self.adj_list = dict[Vertex, list[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},")

图的遍历

广度优先遍历

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

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    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

深度优先遍历

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

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

# 记录被遍历过的节点
visited = []
# 记录从起点到当前节点的路径
onPath = []
# 图的遍历框架
def traverse(graph, s):
    if visited[s]:
        return
    # 经过节点s,标记为已遍历
    visited[s] = True
    # 做选择,标记节点s 在路径上
    onPath[s] = True
    for neighbor in graph.neighbors(s):
        traverse(graph,neighbor)
    # 撤销选择,节点s离开路径
    onPath[s] = False