图算法全景解析 — 从遍历到最短路径与生成树

# 邻接矩阵表示（无向带权图）INF = float('inf')graph_matrix = [    [0,   4,   INF, INF, INF],    [4,   0,   8,   INF, INF],    [INF, 8,   0,   7,   INF],    [INF, INF, 7,   0,   9  ],    [INF, INF, INF, 9,   0  ]]

# 邻接表表示（无向带权图）graph_list = {    0: [(1, 4)],    1: [(0, 4), (2, 8)],    2: [(1, 8), (3, 7)],    3: [(2, 7), (4, 9)],    4: [(3, 9)]}

from collections import deque def bfs(graph, start):    """    广度优先搜索    :param graph: 邻接表，graph[u] = [(v1, w1), (v2, w2), ...] 或 [v1, v2, ...]    :param start: 起始节点    :return: BFS 遍历顺序    """    visited = set()    queue = deque([start])    visited.add(start)    order = []     while queue:        node = queue.popleft()        order.append(node)         for neighbor in graph[node]:            # 兼容带权和无权邻接表            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor            if v not in visited:                visited.add(v)                queue.append(v)     return order # BFS 求无权图最短路径def bfs_shortest_path(graph, start, end):    """    在无权图中求从 start 到 end 的最短路径    """    visited = {start}    queue = deque([(start, [start])])     while queue:        node, path = queue.popleft()        if node == end:            return path         for neighbor in graph[node]:            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor            if v not in visited:                visited.add(v)                queue.append((v, path + [v]))     return None  # 不可达

def dfs_recursive(graph, start, visited=None):    """    深度优先搜索（递归实现）    """    if visited is None:        visited = set()    visited.add(start)    order = [start]     for neighbor in graph[start]:        v = neighbor[0] if isinstance(neighbor, tuple) else neighbor        if v not in visited:            order.extend(dfs_recursive(graph, v, visited))     return order def dfs_iterative(graph, start):    """    深度优先搜索（栈实现）    """    visited = set()    stack = [start]    order = []     while stack:        node = stack.pop()        if node in visited:            continue        visited.add(node)        order.append(node)         # 逆序压栈以保证访问顺序与递归一致        for neighbor in reversed(graph[node]):            v = neighbor[0] if isinstance(neighbor, tuple) else neighbor            if v not in visited:                stack.append(v)     return order

import heapq def dijkstra(graph, start):    """    Dijkstra 单源最短路径算法    :param graph: 邻接表，graph[u] = [(v, weight), ...]    :param start: 起始节点    :return: dist（最短距离字典）, prev（前驱节点字典，用于路径还原）    """    dist = {node: float('inf') for node in graph}    dist[start] = 0    prev = {node: None for node in graph}    # 优先队列：(距离, 节点)    pq = [(0, start)]     while pq:        d, u = heapq.heappop(pq)         # 如果取出的距离已过时，跳过        if d > dist[u]:            continue         for v, weight in graph[u]:            new_dist = dist[u] + weight            if new_dist < dist[v]:                dist[v] = new_dist                prev[v] = u                heapq.heappush(pq, (new_dist, v))     return dist, prev def reconstruct_path(prev, start, end):    """根据前驱节点字典还原路径"""    path = []    current = end    while current is not None:        path.append(current)        current = prev[current]    path.reverse()    return path if path[0] == start else [] # 使用示例graph = {    'A': [('B', 4), ('C', 2)],    'B': [('A', 4), ('C', 1), ('D', 5)],    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],    'D': [('B', 5), ('C', 8), ('E', 2)],    'E': [('C', 10), ('D', 2)]} dist, prev = dijkstra(graph, 'A')print(f"A 到各点最短距离: {dist}")print(f"A 到 E 的最短路径: {reconstruct_path(prev, 'A', 'E')}")

def floyd_warshall(graph_matrix):    """    Floyd-Warshall 全源最短路径    :param graph_matrix: V×V 的邻接矩阵，graph_matrix[i][j] 为边权，无边为 INF    :return: dist 矩阵    """    V = len(graph_matrix)    # 复制矩阵避免修改原数据    dist = [row[:] for row in graph_matrix]     # 核心三重循环：k 为中转点    for k in range(V):        for i in range(V):            for j in range(V):                if dist[i][k] + dist[k][j] < dist[i][j]:                    dist[i][j] = dist[i][k] + dist[k][j]     return dist # 使用示例INF = float('inf')matrix = [    [0,   3,   INF, 7  ],    [8,   0,   2,   INF],    [5,   INF, 0,   1  ],    [2,   INF, INF, 0  ]]result = floyd_warshall(matrix)for row in result:    print(row)

def bellman_ford(vertices, edges, start):    """    Bellman-Ford 单源最短路径（可处理负权边）    :param vertices: 节点列表    :param edges: 边列表，[(u, v, weight), ...]    :param start: 起始节点    :return: dist 字典，若存在负权环返回 None    """    dist = {v: float('inf') for v in vertices}    dist[start] = 0     # V-1 轮松弛    for _ in range(len(vertices) - 1):        for u, v, w in edges:            if dist[u] != float('inf') and dist[u] + w < dist[v]:                dist[v] = dist[u] + w     # 第 V 轮检测负权环    for u, v, w in edges:        if dist[u] != float('inf') and dist[u] + w < dist[v]:            print("图中存在负权环！")            return None     return dist # 使用示例vertices = ['A', 'B', 'C', 'D', 'E']edges = [    ('A', 'B', -1), ('A', 'C', 4),    ('B', 'C', 3),  ('B', 'D', 2), ('B', 'E', 2),    ('D', 'B', 1),  ('D', 'C', 5), ('E', 'D', -3)]print(bellman_ford(vertices, edges, 'A'))

import heapq def prim(graph, start):    """    Prim 最小生成树算法    :param graph: 邻接表，graph[u] = [(v, weight), ...]    :param start: 起始节点    :return: MST 的边列表和总权重    """    mst_edges = []    total_weight = 0    visited = set()    # 优先队列：(权重, 当前节点, 来源节点)    pq = [(0, start, None)]     while pq and len(visited) < len(graph):        weight, u, from_node = heapq.heappop(pq)         if u in visited:            continue         visited.add(u)        total_weight += weight        if from_node is not None:            mst_edges.append((from_node, u, weight))         for v, w in graph[u]:            if v not in visited:                heapq.heappush(pq, (w, v, u))     return mst_edges, total_weight

class UnionFind:    """并查集（路径压缩 + 按秩合并）"""    def __init__(self, n):        self.parent = list(range(n))        self.rank = [0] * n     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):        px, py = self.find(x), self.find(y)        if px == py:            return False  # 已在同一集合，加入会形成环        # 按秩合并        if self.rank[px] < self.rank[py]:            px, py = py, px        self.parent[py] = px        if self.rank[px] == self.rank[py]:            self.rank[px] += 1        return True def kruskal(vertices, edges):    """    Kruskal 最小生成树算法    :param vertices: 节点列表    :param edges: 边列表 [(u, v, weight), ...]    :return: MST 的边列表和总权重    """    # 将节点映射为整数索引    v_map = {v: i for i, v in enumerate(vertices)}    uf = UnionFind(len(vertices))     # 按权重排序    sorted_edges = sorted(edges, key=lambda e: e[2])     mst_edges = []    total_weight = 0     for u, v, w in sorted_edges:        if uf.union(v_map[u], v_map[v]):            mst_edges.append((u, v, w))            total_weight += w            if len(mst_edges) == len(vertices) - 1:                break  # MST 已有 V-1 条边     return mst_edges, total_weight # 使用示例vertices = ['A', 'B', 'C', 'D', 'E']edges = [    ('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1),    ('B', 'D', 5), ('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2)]mst, weight = kruskal(vertices, edges)print(f"最小生成树: {mst}")print(f"总权重: {weight}")

from collections import deque def topological_sort_kahn(graph, vertices):    """    Kahn 算法实现拓扑排序（BFS）    :param graph: 有向图邻接表，graph[u] = [v1, v2, ...]    :param vertices: 所有顶点列表    :return: 拓扑排序结果，若存在环返回 None    """    # 计算所有节点的入度    in_degree = {v: 0 for v in vertices}    for u in graph:        for v in graph[u]:            in_degree[v] = in_degree.get(v, 0) + 1     # 将所有入度为 0 的节点入队    queue = deque([v for v in vertices if in_degree[v] == 0])    result = []     while queue:        node = queue.popleft()        result.append(node)         for neighbor in graph.get(node, []):            in_degree[neighbor] -= 1            if in_degree[neighbor] == 0:                queue.append(neighbor)     # 如果结果长度不等于节点数，说明存在环    if len(result) != len(vertices):        print("图中存在环，无法拓扑排序！")        return None     return result # 使用示例：课程选修顺序course_graph = {    '高等数学': ['线性代数', '概率论'],    '线性代数': ['机器学习'],    '概率论': ['机器学习', '统计学'],    '编程基础': ['数据结构'],    '数据结构': ['算法设计', '机器学习'],    '算法设计': [],    '机器学习': [],    '统计学': []}vertices = list(course_graph.keys())print(topological_sort_kahn(course_graph, vertices))