数据结构（Python）第六章：图

---

6.1 图的定义和基本概念

图是由顶点（Vertex）和边（Edge）组成的非线性数据结构，分为无向图和有向图。
基本术语：

• 顶点（Vertex）：图中的基本元素（节点）。
• 边（Edge）：连接两个顶点的线，可带权重。
• 路径：顶点间边的序列。
• 环：起点和终点相同的路径。
• 连通图：任意两顶点间都存在路径。

---

6.2 图的存储结构

6.2.1 邻接矩阵（Adjacency Matrix）

用二维数组存储顶点间的邻接关系，适合稠密图。

python">class GraphAdjMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices  # 顶点数量
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]  # 初始化邻接矩阵

    def add_edge(self, u, v, weight=1):
        """添加边（无向图默认双向）"""
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight  # 若为有向图，注释此行

    def remove_edge(self, u, v):
        """删除边"""
        self.matrix[u][v] = 0
        self.matrix[v][u] = 0

    def has_edge(self, u, v):
        """检查是否存在边"""
        return self.matrix[u][v] != 0

    def __str__(self):
        """打印邻接矩阵"""
        return "\n".join([" ".join(map(str, row)) for row in self.matrix])

6.2.2 邻接表（Adjacency List）

用链表存储每个顶点的邻接顶点，适合稀疏图。

python">class GraphNode:
    def __init__(self, vertex):
        self.vertex = vertex       # 邻接顶点
        self.next = None           # 下一邻接节点指针

class GraphAdjList:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [None] * num_vertices  # 初始化邻接表

    def add_edge(self, u, v, weight=1):
        """添加边（无向图需添加两次）"""
        # 添加 u -> v 的边
        new_node = GraphNode(v)
        new_node.next = self.adj_list[u]
        self.adj_list[u] = new_node
        # 添加 v -> u 的边（若为有向图，注释此部分）
        new_node = GraphNode(u)
        new_node.next = self.adj_list[v]
        self.adj_list[v] = new_node

    def remove_edge(self, u, v):
        """删除边（需处理双向）"""
        # 删除 u -> v 的边
        current = self.adj_list[u]
        prev = None
        while current and current.vertex != v:
            prev = current
            current = current.next
        if current:
            if prev:
                prev.next = current.next
            else:
                self.adj_list[u] = current.next
        # 删除 v -> u 的边（若为有向图，注释此部分）
        current = self.adj_list[v]
        prev = None
        while current and current.vertex != u:
            prev = current
            current = current.next
        if current:
            if prev:
                prev.next = current.next
            else:
                self.adj_list[v] = current.next

    def has_edge(self, u, v):
        """检查是否存在边 u->v"""
        current = self.adj_list[u]
        while current:
            if current.vertex == v:
                return True
            current = current.next
        return False

    def print_graph(self):
        """打印邻接表"""
        for i in range(self.num_vertices):
            print(f"顶点 {i}: ", end="")
            current = self.adj_list[i]
            while current:
                print(f"-> {current.vertex}", end="")
                current = current.next
            print()

---

6.3 图的遍历算法

6.3.1 深度优先搜索（DFS）

递归实现：优先深入访问未探索的路径。

python">def dfs(graph, start, visited=None):
    """深度优先搜索（递归）"""
    if visited is None:
        visited = set()  # 记录已访问顶点
    visited.add(start)
    print(f"访问顶点: {start}")

    current = graph.adj_list[start]
    while current:
        neighbor = current.vertex
        if neighbor not in visited:
            dfs(graph, neighbor, visited)  # 递归访问未探索邻接点
        current = current.next

6.3.2 广度优先搜索（BFS）

队列实现：按层级逐层访问。

python">from collections import deque

def bfs(graph, start):
    """广度优先搜索（队列）"""
    visited = set()
    queue = deque([start])  # 初始化队列
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(f"访问顶点: {vertex}")

        current = graph.adj_list[vertex]
        while current:
            neighbor = current.vertex
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # 邻接点入队
            current = current.next

---

6.4 最小生成树算法

6.4.1 Prim 算法

贪心策略：从顶点出发，逐步扩展最小边。

python">import heapq

def prim_mst(graph):
    """Prim算法求最小生成树（返回边列表）"""
    num_vertices = graph.num_vertices
    visited = [False] * num_vertices
    min_heap = []  # 优先队列存储 (权重, u, v)
    mst_edges = []

    # 从顶点0开始
    visited[0] = True
    current = graph.adj_list[0]
    while current:
        heapq.heappush(min_heap, (1, 0, current.vertex))  # 假设权重为1
        current = current.next

    while min_heap and len(mst_edges) < num_vertices - 1:
        weight, u, v = heapq.heappop(min_heap)
        if not visited[v]:
            visited[v] = True
            mst_edges.append((u, v, weight))
            # 将v的邻接边加入堆
            current = graph.adj_list[v]
            while current:
                if not visited[current.vertex]:
                    heapq.heappush(min_heap, (1, v, current.vertex))
                current = current.next

    return mst_edges

6.4.2 Kruskal 算法

并查集优化：按权重排序边，避免环。

python">class UnionFind:
    """并查集（支持路径压缩和按秩合并）"""
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # 已在同一集合
        # 按秩合并
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_y] += 1
        return True

def kruskal_mst(graph):
    """Kruskal算法求最小生成树"""
    edges = []
    # 收集所有边（假设权重为1）
    for u in range(graph.num_vertices):
        current = graph.adj_list[u]
        while current:
            edges.append((1, u, current.vertex))  # (weight, u, v)
            current = current.next
    edges.sort()  # 按权重排序
    uf = UnionFind(graph.num_vertices)
    mst_edges = []

    for edge in edges:
        weight, u, v = edge
        if uf.union(u, v):
            mst_edges.append((u, v, weight))
    return mst_edges

---

6.5 最短路径算法

6.5.1 Dijkstra 算法（无负权边）

python">import heapq

def dijkstra(graph, start):
    """Dijkstra算法求单源最短路径"""
    num_vertices = graph.num_vertices
    distances = [float('inf')] * num_vertices
    distances[start] = 0
    heap = [(0, start)]  # (distance, vertex)

    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > distances[u]:
            continue  # 已找到更优路径
        # 遍历邻接顶点
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            weight = 1  # 假设边权重为1
            if distances[v] > distances[u] + weight:
                distances[v] = distances[u] + weight
                heapq.heappush(heap, (distances[v], v))
            current = current.next
    return distances

6.5.2 Floyd-Warshall 算法（多源最短路径）

python">def floyd_warshall(graph):
    """Floyd-Warshall算法求所有顶点对最短路径"""
    num_vertices = graph.num_vertices
    dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    # 初始化邻接矩阵
    for u in range(num_vertices):
        dist[u][u] = 0
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            dist[u][v] = 1  # 假设权重为1
            current = current.next
    # 动态规划更新最短路径
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

---

6.6 拓扑排序（针对有向无环图）

python">def topological_sort(graph):
    """拓扑排序（返回顶点顺序）"""
    num_vertices = graph.num_vertices
    in_degree = [0] * num_vertices
    # 计算入度
    for u in range(num_vertices):
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            in_degree[v] += 1
            current = current.next
    # 初始化队列（入度为0的顶点）
    queue = deque([u for u in range(num_vertices) if in_degree[u] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        # 更新邻接顶点的入度
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
            current = current.next
    # 检查是否存在环
    if len(result) != num_vertices:
        return None  # 存在环，无法拓扑排序
    return result

---

6.7 关键路径（AOE网）

python">def critical_path(graph):
    """计算关键路径（返回关键活动列表）"""
    topo_order = topological_sort(graph)
    if not topo_order:
        return None  # 存在环，无法计算

    num_vertices = graph.num_vertices
    earliest = [0] * num_vertices
    # 正向计算最早发生时间
    for u in topo_order:
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            weight = 1  # 假设活动时间为1
            if earliest[v] < earliest[u] + weight:
                earliest[v] = earliest[u] + weight
            current = current.next
    # 反向计算最晚发生时间
    latest = [earliest[-1]] * num_vertices
    for u in reversed(topo_order):
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            weight = 1
            if latest[u] > latest[v] - weight:
                latest[u] = latest[v] - weight
            current = current.next
    # 提取关键活动（最早时间 == 最晚时间）
    critical_edges = []
    for u in range(num_vertices):
        current = graph.adj_list[u]
        while current:
            v = current.vertex
            weight = 1
            if earliest[u] == latest[v] - weight:
                critical_edges.append((u, v, weight))
            current = current.next
    return critical_edges

---

6.8 总结

本章详细实现了图的存储结构（邻接矩阵、邻接表）、遍历算法（DFS、BFS）、最小生成树（Prim、Kruskal）、最短路径（Dijkstra、Floyd-Warshall）、拓扑排序及关键路径，所有代码均添加详细注释。通过合理选择数据结构与算法，可高效解决路径规划、任务调度等实际问题。