图算法（Graph Algorithms）完全详解 - 从零到网络流¶

class GraphMatrix:
    """使用邻接矩阵实现无向图"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 创建num_vertices × num_vertices的矩阵
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, i, j, weight=1):
        """添加边（无向图是对称的）"""
        if 0 <= i < self.num_vertices and 0 <= j < self.num_vertices:
            self.matrix[i][j] = weight
            self.matrix[j][i] = weight  # 无向图是对称的
            print(f"添加边: {i} ←→ {j} (权重={weight})")

    def remove_edge(self, i, j):
        """删除边"""
        if 0 <= i < self.num_vertices and 0 <= j < self.num_vertices:
            self.matrix[i][j] = 0
            self.matrix[j][i] = 0
            print(f"删除边: {i} ←→ {j}")

    def has_edge(self, i, j):
        """检查边是否存在：O(1)"""
        return self.matrix[i][j] != 0

    def get_neighbors(self, v):
        """获取顶点v的所有邻居：O(V)"""
        neighbors = []
        for i in range(self.num_vertices):
            if self.matrix[v][i] != 0:
                neighbors.append((i, self.matrix[v][i]))
        return neighbors

    def print_matrix(self):
        """打印邻接矩阵"""
        print("\n邻接矩阵:")
        print("   ", end="")
        for i in range(self.num_vertices):
            print(f"{i:3}", end="")
        print()

        for i in range(self.num_vertices):
            print(f"{i:2} ", end="")
            for j in range(self.num_vertices):
                print(f"{self.matrix[i][j]:3}", end="")
            print()

# 测试
graph = GraphMatrix(5)
print("=" * 60)
print("邻接矩阵测试")
print("=" * 60)

# 添加边（构建如下图）
#     0
#    / \
#   1---2
#   |   |
#   3---4

graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)

graph.print_matrix()

# 输出：
# ============================================================
# 邻接矩阵测试
# ============================================================
# 添加边: 0 ←→ 1 (权重=1)
# 添加边: 0 ←→ 2 (权重=1)
# 添加边: 1 ←→ 2 (权重=1)
# 添加边: 1 ←→ 3 (权重=1)
# 添加边: 2 ←→ 4 (权重=1)
# 添加边: 3 ←→ 4 (权重=1)
#
# 邻接矩阵:
#       0  1  2  3  4
#  0   0  1  1  0  0
#  1   1  0  1  1  0
#  2   1  1  0  0  1
#  3   0  1  0  0  1
#  4   0  0  1  1  0
#
# 特点：
# - 对角线为0（自己到自己）
# - 对称矩阵（无向图）
# - 第i行的和 = 顶点i的度

class WeightedDiGraphMatrix:
    """带权有向图的邻接矩阵"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 使用float('inf')表示无穷大（没有边）
        self.matrix = [[float('inf')] * num_vertices for _ in range(num_vertices)]
        # 对角线设为0（自己到自己的距离为0）
        for i in range(num_vertices):
            self.matrix[i][i] = 0

    def add_edge(self, i, j, weight):
        """添加有向边"""
        if 0 <= i < self.num_vertices and 0 <= j < self.num_vertices:
            self.matrix[i][j] = weight
            print(f"添加边: {i} → {j} (权重={weight})")

    def print_matrix(self):
        """打印邻接矩阵"""
        print("\n邻接矩阵（带权有向图）:")
        print("     ", end="")
        for i in range(self.num_vertices):
            print(f"{i:6}", end="")
        print()

        for i in range(self.num_vertices):
            print(f"{i:2} ", end="")
            for j in range(self.num_vertices):
                val = self.matrix[i][j]
                if val == float('inf'):
                    print(f"   INF", end="")
                else:
                    print(f"{val:6}", end="")
            print()

# 测试
print("\n" + "=" * 60)
print("带权有向图测试")
print("=" * 60)

wg = WeightedDiGraphMatrix(4)

# 构建如下带权有向图：
#     10     20
#  0 ----> 1 ----> 2
#  ^       |      /^
#  |5     |15   /1
#  3 ---->-----   |
#      8
#
# 注：箭头表示边的方向

wg.add_edge(0, 1, 10)
wg.add_edge(1, 2, 20)
wg.add_edge(1, 3, 15)
wg.add_edge(3, 0, 5)
wg.add_edge(3, 1, 8)
wg.add_edge(2, 3, 1)

wg.print_matrix()

# 输出：
# ============================================================
# 带权有向图测试
# ============================================================
# 添加边: 0 → 1 (权重=10)
# 添加边: 1 → 2 (权重=20)
# 添加边: 1 → 3 (权重=15)
# 添加边: 3 → 0 (权重=5)
# 添加边: 3 → 1 (权重=8)
# 添加边: 2 → 3 (权重=1)
#
# 邻接矩阵（带权有向图）:
#          0      1      2      3
#  0       0     10    INF    INF
#  1     INF       0     20     15
#  2     INF     INF      0      1
#  3       5      8    INF      0
#
# 特点：
# - 非对称矩阵（有向图）
# - INF表示没有边

class GraphAdjList:
    """使用邻接表实现无向图"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 每个顶点对应一个列表，存储邻居
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, i, j, weight=1):
        """添加边"""
        if 0 <= i < self.num_vertices and 0 <= j < self.num_vertices:
            self.adj_list[i].append((j, weight))
            self.adj_list[j].append((i, weight))  # 无向图要双向添加
            print(f"添加边: {i} ←→ {j} (权重={weight})")

    def remove_edge(self, i, j):
        """删除边"""
        if 0 <= i < self.num_vertices and 0 <= j < self.num_vertices:
            # 从i的邻居列表中删除j
            self.adj_list[i] = [(v, w) for v, w in self.adj_list[i] if v != j]
            # 从j的邻居列表中删除i
            self.adj_list[j] = [(v, w) for v, w in self.adj_list[j] if v != i]
            print(f"删除边: {i} ←→ {j}")

    def has_edge(self, i, j):
        """检查边是否存在：O(度数)"""
        for v, w in self.adj_list[i]:
            if v == j:
                return True
        return False

    def get_neighbors(self, v):
        """获取顶点v的所有邻居：O(度数)"""
        return self.adj_list[v]

    def print_adj_list(self):
        """打印邻接表"""
        print("\n邻接表:")
        for i in range(self.num_vertices):
            neighbors = ", ".join([f"({v},w={w})" for v, w in self.adj_list[i]])
            print(f"  {i}: [{neighbors}]")

# 测试
graph = GraphAdjList(5)
print("=" * 60)
print("邻接表测试")
print("=" * 60)

# 构建相同的图
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)

graph.print_adj_list()

# 输出：
# ============================================================
# 邻接表测试
# ============================================================
# 添加边: 0 ←→ 1 (权重=1)
# 添加边: 0 ←→ 2 (权重=1)
# 添加边: 1 ←→ 2 (权重=1)
# 添加边: 1 ←→ 3 (权重=1)
# 添加边: 2 ←→ 4 (权重=1)
# 添加边: 3 ←→ 4 (权重=1)
#
# 邻接表:
#   0: [(1,w=1), (2,w=1)]
#   1: [(0,w=1), (2,w=1), (3,w=1)]
#   2: [(0,w=1), (1,w=1), (4,w=1)]
#   3: [(1,w=1), (4,w=1)]
#   4: [(2,w=1), (3,w=1)]

class GraphDict:
    """使用字典实现邻接表（更灵活）"""

    def __init__(self):
        # 字典：顶点 -> [(邻居, 权重), ...]
        self.graph = {}

    def add_vertex(self, vertex):
        """添加顶点"""
        if vertex not in self.graph:
            self.graph[vertex] = []
            print(f"添加顶点: {vertex}")

    def add_edge(self, v1, v2, weight=1, directed=False):
        """添加边"""
        if v1 not in self.graph or v2 not in self.graph:
            print(f"错误：顶点不存在")
            return

        self.graph[v1].append((v2, weight))
        print(f"添加边: {v1} → {v2} (权重={weight})")

        if not directed:  # 无向图，反向也要添加
            self.graph[v2].append((v1, weight))
            print(f"添加边: {v2} → {v1} (权重={weight})")

    def get_neighbors(self, vertex):
        """获取邻居"""
        return self.graph.get(vertex, [])

    def print_graph(self):
        """打印图"""
        print("\n图的邻接表表示:")
        for vertex in sorted(self.graph.keys()):
            neighbors = ", ".join([f"{v}(w={w})" for v, w in self.graph[vertex]])
            print(f"  {vertex}: [{neighbors}]")

# 测试：城市交通网络
print("\n" + "=" * 60)
print("城市交通网络（带权无向图）")
print("=" * 60)

cities = GraphDict()

# 添加城市
for city in ['北京', '上海', '广州', '深圳', '成都']:
    cities.add_vertex(city)

# 添加路线（距离单位：公里）
cities.add_edge('北京', '上海', 1200)
cities.add_edge('北京', '成都', 1800)
cities.add_edge('上海', '广州', 1400)
cities.add_edge('广州', '深圳', 140)
cities.add_edge('成都', '广州', 1600)

cities.print_graph()

# 输出：
# ============================================================
# 城市交通网络（带权无向图）
# ============================================================
# 添加顶点: 北京
# 添加顶点: 上海
# 添加顶点: 广州
# 添加顶点: 深圳
# 添加顶点: 成都
# 添加边: 北京 → 上海 (权重=1200)
# 添加边: 上海 → 北京 (权重=1200)
# 添加边: 北京 → 成都 (权重=1800)
# 添加边: 成都 → 北京 (权重=1800)
# 添加边: 上海 → 广州 (权重=1400)
# 添加边: 广州 → 上海 (权重=1400)
# 添加边: 广州 → 深圳 (权重=140)
# 添加边: 深圳 → 广州 (权重=140)
# 添加边: 成都 → 广州 (权重=1600)
# 添加边: 广州 → 成都 (权重=1600)
#
# 图的邻接表表示:
#   上海: [(北京,w=1200), (广州,w=1400)]
#   北京: [(上海,w=1200), (成都,w=1800)]
#   广州: [(上海,w=1400), (深圳,w=140), (成都,w=1600)]
#   成都: [(北京,w=1800), (广州,w=1600)]
#   深圳: [(广州,w=140)]

class GraphDFS:
    """图的DFS遍历"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, i, j):
        """添加边"""
        self.adj_list[i].append(j)
        self.adj_list[j].append(i)

    def dfs_recursive(self, start=0):
        """
        DFS递归实现
        时间：O(V+E)
        空间：O(V)（递归栈 + visited数组）
        """
        visited = [False] * self.num_vertices
        result = []

        def dfs_helper(vertex):
            visited[vertex] = True
            result.append(vertex)
            print(f"  访问顶点: {vertex}")

            # 递归访问所有未访问的邻居
            for neighbor in self.adj_list[vertex]:
                if not visited[neighbor]:
                    dfs_helper(neighbor)

        print(f"\n从顶点{start}开始DFS（递归）:")
        dfs_helper(start)
        return result

    def dfs_iterative(self, start=0):
        """
        DFS迭代实现（使用栈）
        时间：O(V+E)
        空间：O(V)
        """
        visited = [False] * self.num_vertices
        result = []
        stack = [start]

        print(f"\n从顶点{start}开始DFS（迭代）:")

        while stack:
            vertex = stack.pop()

            if not visited[vertex]:
                visited[vertex] = True
                result.append(vertex)
                print(f"  访问顶点: {vertex}")

                # 将邻居加入栈（倒序加入，保证顺序一致）
                for neighbor in reversed(self.adj_list[vertex]):
                    if not visited[neighbor]:
                        stack.append(neighbor)

        return result

    def dfs_all_components(self):
        """遍历所有连通分量"""
        visited = [False] * self.num_vertices
        result = []
        component_id = 0

        print("\n遍历所有连通分量:")

        for vertex in range(self.num_vertices):
            if not visited[vertex]:
                print(f"\n连通分量 {component_id}:")
                component = []

                def dfs(v):
                    visited[v] = True
                    component.append(v)
                    print(f"  访问: {v}")

                    for neighbor in self.adj_list[v]:
                        if not visited[neighbor]:
                            dfs(neighbor)

                dfs(vertex)
                result.append(component)
                component_id += 1

        return result

# 测试
print("=" * 60)
print("DFS遍历测试")
print("=" * 60)

# 构建如下图：
#       0
#      /|\
#     1 2 3
#    /|   |
#   4 5   6
#
#  7-8（孤立连通分量）

graph = GraphDFS(9)
edges = [(0,1), (0,2), (0,3), (1,4), (1,5), (3,6), (7,8)]
for i, j in edges:
    graph.add_edge(i, j)

result1 = graph.dfs_recursive(0)
print(f"\nDFS递归结果: {result1}")

result2 = graph.dfs_iterative(0)
print(f"\nDFS迭代结果: {result2}")

components = graph.dfs_all_components()
print(f"\n共找到 {len(components)} 个连通分量")

# 输出：
# ============================================================
# DFS遍历测试
# ============================================================
#
# 从顶点0开始DFS（递归）:
#   访问顶点: 0
#   访问顶点: 1
#   访问顶点: 4
#   访问顶点: 5
#   访问顶点: 2
#   访问顶点: 3
#   访问顶点: 6
#
# DFS递归结果: [0, 1, 4, 5, 2, 3, 6]
#
# 从顶点0开始DFS（迭代）:
#   访问顶点: 0
#   访问顶点: 1
#   访问顶点: 4
#   访问顶点: 5
#   访问顶点: 2
#   访问顶点: 3
#   访问顶点: 6
#
# DFS迭代结果: [0, 1, 4, 5, 2, 3, 6]
#
# 遍历所有连通分量:
#
# 连通分量 0:
#   访问: 0
#   访问: 1
#   访问: 4
#   访问: 5
#   访问: 2
#   访问: 3
#   访问: 6
#
# 连通分量 1:
#   访问: 7
#   访问: 8
#
# 共找到 2 个连通分量

from collections import deque

class GraphBFS:
    """图的BFS遍历"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, i, j):
        """添加边"""
        self.adj_list[i].append(j)
        self.adj_list[j].append(i)

    def bfs(self, start=0):
        """
        BFS实现
        时间：O(V+E)
        空间：O(V)
        """
        visited = [False] * self.num_vertices
        result = []
        queue = deque([start])
        visited[start] = True

        print(f"从顶点{start}开始BFS:")

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

            # 将所有未访问的邻居加入队列
            for neighbor in self.adj_list[vertex]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        return result

    def bfs_level_by_level(self, start=0):
        """BFS分层遍历（更详细）"""
        visited = [False] * self.num_vertices
        queue = deque([start])
        visited[start] = True
        level = 0

        print(f"\n从顶点{start}开始BFS（分层）:")

        while queue:
            level_size = len(queue)
            print(f"\n第{level}层: ", end="")

            for _ in range(level_size):
                vertex = queue.popleft()
                print(f"{vertex}", end=" ")

                for neighbor in self.adj_list[vertex]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

            level += 1

        print()

    def bfs_shortest_path(self, start, end):
        """BFS求最短路径（无权图）"""
        if start == end:
            return [start], 0

        visited = [False] * self.num_vertices
        parent = [-1] * self.num_vertices  # 记录路径
        queue = deque([start])
        visited[start] = True

        print(f"\n求从{start}到{end}的最短路径:")

        while queue:
            vertex = queue.popleft()

            for neighbor in self.adj_list[vertex]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = vertex
                    queue.append(neighbor)

                    if neighbor == end:
                        # 找到目标，回溯路径
                        path = []
                        current = end
                        while current != -1:
                            path.append(current)
                            current = parent[current]
                        path.reverse()

                        print(f"  路径: {path}")
                        print(f"  长度: {len(path) - 1}")
                        return path, len(path) - 1

        print("  未找到路径")
        return None, -1

# 测试
print("\n" + "=" * 60)
print("BFS遍历测试")
print("=" * 60)

# 使用相同的图
graph = GraphBFS(9)
edges = [(0,1), (0,2), (0,3), (1,4), (1,5), (3,6), (7,8)]
for i, j in edges:
    graph.add_edge(i, j)

result = graph.bfs(0)
print(f"\nBFS结果: {result}")

graph.bfs_level_by_level(0)

path, length = graph.bfs_shortest_path(0, 6)
print(f"\n最短路径验证:")
print(f"  从0到6: {path} (长度={length})")

# 输出：
# ============================================================
# BFS遍历测试
# ============================================================
# 从顶点0开始BFS:
#   访问顶点: 0
#   访问顶点: 1
#   访问顶点: 2
#   访问顶点: 3
#   访问顶点: 4
#   访问顶点: 5
#   访问顶点: 6
#
# BFS结果: [0, 1, 2, 3, 4, 5, 6]
#
# 从顶点0开始BFS（分层）:
#
# 第0层: 0
# 第1层: 1 2 3
# 第2层: 4 5 6
#
# 求从0到6的最短路径:
#   路径: [0, 3, 6]
#   长度: 2
#
# 最短路径验证:
#   从0到6: [0, 3, 6] (长度=2)

import heapq

class DijkstraGraph:
    """Dijkstra算法实现"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, i, j, weight, directed=True):
        """添加边"""
        self.adj_list[i].append((j, weight))
        if not directed:
            self.adj_list[j].append((i, weight))

    def dijkstra(self, start):
        """
        Dijkstra算法（优先队列优化）
        时间：O((V+E)log V)
        空间：O(V)
        """
        # 初始化距离
        dist = [float('inf')] * self.num_vertices
        dist[start] = 0

        # 记录路径
        parent = [-1] * self.num_vertices

        # 最小堆：(距离, 顶点)
        heap = [(0, start)]
        visited = [False] * self.num_vertices

        print(f"\n从顶点{start}开始Dijkstra算法:")
        print("=" * 60)

        while heap:
            current_dist, vertex = heapq.heappop(heap)

            # 如果已经访问过，跳过
            if visited[vertex]:
                continue

            visited[vertex] = True
            print(f"\n访问顶点 {vertex} (当前距离={current_dist})")

            # 遍历所有邻居
            for neighbor, weight in self.adj_list[vertex]:
                if not visited[neighbor]:
                    new_dist = current_dist + weight

                    # 松弛操作：如果找到更短的路径
                    if new_dist < dist[neighbor]:
                        dist[neighbor] = new_dist
                        parent[neighbor] = vertex
                        heapq.heappush(heap, (new_dist, neighbor))
                        print(f"  更新: {vertex} → {neighbor} (新距离={new_dist})")

        return dist, parent

    def print_path(self, parent, start, end):
        """打印路径"""
        if parent[end] == -1 and start != end:
            print(f"  {start} 到 {end}: 不可达")
            return

        path = []
        current = end
        while current != -1:
            path.append(current)
            current = parent[current]
        path.reverse()

        print(f"  最短路径: {' → '.join(map(str, path))}")

    def dijkstra_detailed(self, start):
        """Dijkstra详细版（展示每一步）"""
        dist, parent = self.dijkstra(start)

        print("\n" + "=" * 60)
        print("最终结果:")
        print("=" * 60)

        for i in range(self.num_vertices):
            if dist[i] == float('inf'):
                print(f"{start} → {i}: 不可达")
            else:
                print(f"{start} → {i}: 距离={dist[i]}", end="")
                if i != start:
                    print(", 路径=", end="")
                    self.print_path(parent, start, i)
                else:
                    print()

# 测试
print("=" * 60)
print("Dijkstra算法测试")
print("=" * 60)

graph = DijkstraGraph(5)

# 构建图：
#     10    30
#  0 ----> 1 ----> 2
#  |       |      /^
# 5|      15|   /1
#  v       v  /
#  3 ---->----
#      8
# 注：顶点4未连接任何边，用于展示不可达情况

graph.add_edge(0, 1, 10)
graph.add_edge(0, 3, 5)
graph.add_edge(1, 2, 30)
graph.add_edge(1, 3, 15)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 1, 8)

dist, parent = graph.dijkstra(0)

# 输出：
# ============================================================
# Dijkstra算法测试
# ============================================================
#
# 从顶点0开始Dijkstra算法:
# =============================================================
#
# 访问顶点 0 (当前距离=0)
#   更新: 0 → 1 (新距离=10)
#   更新: 0 → 3 (新距离=5)
#
# 访问顶点 3 (当前距离=5)
#   更新: 3 → 2 (新距离=6)
#   （检查 3 → 1: 距离=13 > 当前dist[1]=10，不更新）
#
# 访问顶点 2 (当前距离=6)
#
# 访问顶点 1 (当前距离=10)
#
# =============================================================
# 最终结果:
# =============================================================
# 0 → 0: 距离=0
# 0 → 1: 距离=10, 路径=  最短路径: 0 → 1
# 0 → 2: 距离=6, 路径=  最短路径: 0 → 3 → 2
# 0 → 3: 距离=5, 路径=  最短路径: 0 → 3
# 0 → 4: 不可达

class BellmanFordGraph:
    """Bellman-Ford算法实现"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.edges = []  # 边列表：(u, v, weight)

    def add_edge(self, u, v, weight):
        """添加边"""
        self.edges.append((u, v, weight))
        print(f"添加边: {u} → {v} (权重={weight})")

    def bellman_ford(self, start):
        """
        Bellman-Ford算法
        时间：O(VE)
        空间：O(V)
        """
        # 初始化
        dist = [float('inf')] * self.num_vertices
        dist[start] = 0
        parent = [-1] * self.num_vertices

        print(f"\n从顶点{start}开始Bellman-Ford算法:")
        print("=" * 60)

        # 松弛所有边 V-1 次
        for i in range(self.num_vertices - 1):
            print(f"\n第{i+1}轮松弛:")
            updated = False

            for u, v, weight in self.edges:
                if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    parent[v] = u
                    updated = True
                    print(f"  松弛: {u} → {v}, 更新dist[{v}]={dist[v]}")

            if not updated:
                print("  无更新，提前结束")
                break

        # 检测负权环
        print("\n检测负权环:")
        for u, v, weight in self.edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                print("  发现负权环！")
                return None, None

        print("  无负权环 ✓")

        return dist, parent

# 测试
print("\n" + "=" * 60)
print("Bellman-Ford算法测试")
print("=" * 60)

graph = BellmanFordGraph(5)

# 构建图（含负权边）
graph.add_edge(0, 1, 6)
graph.add_edge(0, 2, 7)
graph.add_edge(1, 2, 8)
graph.add_edge(1, 3, -4)
graph.add_edge(1, 4, 5)
graph.add_edge(2, 3, 9)
graph.add_edge(2, 4, -3)
graph.add_edge(3, 4, 7)
graph.add_edge(4, 1, -2)

dist, parent = graph.bellman_ford(0)

if dist:
    print("\n最终距离:")
    for i, d in enumerate(dist):  # enumerate同时获取索引和值
        if d != float('inf'):
            print(f"  0 → {i}: {d}")

# 输出：
# ============================================================
# Bellman-Ford算法测试
# ============================================================
# 添加边: 0 → 1 (权重=6)
# 添加边: 0 → 2 (权重=7)
# 添加边: 1 → 2 (权重=8)
# 添加边: 1 → 3 (权重=-4)
# 添加边: 1 → 4 (权重=5)
# 添加边: 2 → 3 (权重=9)
# 添加边: 2 → 4 (权重=-3)
# 添加边: 3 → 4 (权重=7)
# 添加边: 4 → 1 (权重=-2)
#
# 从顶点0开始Bellman-Ford算法:
# =============================================================
#
# 第1轮松弛:
#   松弛: 0 → 1, 更新dist[1]=6
#   松弛: 0 → 2, 更新dist[2]=7
#   松弛: 1 → 3, 更新dist[3]=2
#   松弛: 1 → 4, 更新dist[4]=11
#   松弛: 2 → 4, 更新dist[4]=4
#   松弛: 4 → 1, 更新dist[1]=2
#
# 第2轮松弛:
#   松弛: 1 → 3, 更新dist[3]=-2
#
# 第3轮松弛:
#   无更新，提前结束
#
# 检测负权环:
#   无负权环 ✓
#
# 最终距离:
#   0 → 0: 0
#   0 → 1: 2
#   0 → 2: 7
#   0 → 3: -2
#   0 → 4: 4

class FloydWarshallGraph:
    """Floyd-Warshall算法实现"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 初始化距离矩阵
        self.dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
        for i in range(num_vertices):
            self.dist[i][i] = 0
        self.next = [[-1] * num_vertices for _ in range(num_vertices)]  # 负索引：从末尾倒数访问元素

    def add_edge(self, i, j, weight):
        """添加边"""
        self.dist[i][j] = weight
        self.next[i][j] = j
        print(f"添加边: {i} → {j} (权重={weight})")

    def floyd_warshall(self):
        """
        Floyd-Warshall算法
        时间：O(V³)
        空间：O(V²)
        """
        print(f"\nFloyd-Warshall算法:")
        print("=" * 60)

        # 三重循环：考虑每个顶点作为中间点
        for k in range(self.num_vertices):
            print(f"\n考虑顶点{k}作为中间点:")
            for i in range(self.num_vertices):
                for j in range(self.num_vertices):
                    # 通过k的路径是否更短
                    if self.dist[i][k] + self.dist[k][j] < self.dist[i][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]
                        self.next[i][j] = self.next[i][k]
                        print(f"  更新: {i} → {k} → {j} (新距离={self.dist[i][j]})")

        # 检测负权环
        print("\n检测负权环:")
        for i in range(self.num_vertices):
            if self.dist[i][i] < 0:
                print(f"  发现负权环！顶点{i}")
                return False

        print("  无负权环 ✓")
        return True

    def print_distance_matrix(self):
        """打印距离矩阵"""
        print("\n距离矩阵:")
        print("     ", end="")
        for j in range(self.num_vertices):
            print(f"{j:6}", end="")
        print()

        for i in range(self.num_vertices):
            print(f"{i:2} ", end="")
            for j in range(self.num_vertices):
                val = self.dist[i][j]
                if val == float('inf'):
                    print(f"  INF ", end="")
                else:
                    print(f"{val:6}", end="")
            print()

    def reconstruct_path(self, i, j):
        """重建路径"""
        if self.next[i][j] == -1:
            return None

        path = []
        while i != j:
            path.append(i)
            i = self.next[i][j]
        path.append(j)

        return path

# 测试
print("\n" + "=" * 60)
print("Floyd-Warshall算法测试")
print("=" * 60)

graph = FloydWarshallGraph(4)

# 构建图
graph.add_edge(0, 1, 3)
graph.add_edge(0, 2, 6)
graph.add_edge(1, 2, 2)
graph.add_edge(1, 3, 7)
graph.add_edge(2, 3, 1)

success = graph.floyd_warshall()

if success:
    graph.print_distance_matrix()

    # 示例：重建路径
    print("\n示例路径:")
    path = graph.reconstruct_path(0, 3)
    if path:
        print(f"  0 → 3: {' → '.join(map(str, path))}, 距离={graph.dist[0][3]}")

# 输出：
# ============================================================
# Floyd-Warshall算法测试
# ============================================================
# 添加边: 0 → 1 (权重=3)
# 添加边: 0 → 2 (权重=6)
# 添加边: 1 → 2 (权重=2)
# 添加边: 1 → 3 (权重=7)
# 添加边: 2 → 3 (权重=1)
#
# Floyd-Warshall算法:
# =============================================================
#
# 考虑顶点0作为中间点:
#   （无更新）
#
# 考虑顶点1作为中间点:
#   更新: 0 → 1 → 2 (新距离=5)
#   更新: 0 → 1 → 3 (新距离=10)
#
# 考虑顶点2作为中间点:
#   更新: 0 → 2 → 3 (新距离=6)
#   更新: 1 → 2 → 3 (新距离=3)
#
# 考虑顶点3作为中间点:
#
# 检测负权环:
#   无负权环 ✓
#
# 距离矩阵:
#          0      1      2      3
#  0      0      3      5      6
#  1    INF      0      2      3
#  2    INF    INF      0      1
#  3    INF    INF    INF      0
#
# 示例路径:
#   0 → 3: 0 → 1 → 2 → 3, 距离=6

import heapq

class PrimMST:
    """Prim算法求MST"""

    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, i, j, weight):
        """添加边"""
        self.adj_list[i].append((j, weight))
        self.adj_list[j].append((i, weight))

    def prim_mst(self, start=0):
        """
        Prim算法
        时间：O((V+E)log V)
        空间：O(V)
        """
        visited = [False] * self.num_vertices
        mst_edges = []
        total_weight = 0

        # 最小堆：(权重, 当前顶点, 父顶点)
        heap = [(0, start, -1)]

        print(f"\nPrim算法（从顶点{start}开始）:")
        print("=" * 60)

        while heap and len(mst_edges) < self.num_vertices - 1:
            weight, vertex, parent = heapq.heappop(heap)

            if visited[vertex]:
                continue

            visited[vertex] = True

            if parent != -1:
                mst_edges.append((parent, vertex, weight))
                total_weight += weight
                print(f"添加边: {parent} ←→ {vertex} (权重={weight})")

            # 将所有未访问邻居加入堆
            for neighbor, edge_weight in self.adj_list[vertex]:
                if not visited[neighbor]:
                    heapq.heappush(heap, (edge_weight, neighbor, vertex))

        print(f"\nMST总权重: {total_weight}")
        return mst_edges, total_weight

# 测试
print("=" * 60)
print("Prim算法测试")
print("=" * 60)

graph = PrimMST(6)

# 构建示例图
edges = [
    (0, 1, 2), (0, 3, 4),
    (1, 2, 3), (1, 3, 5), (1, 4, 1),
    (2, 4, 6),
    (3, 4, 8), (3, 5, 7),
    (4, 5, 9)
]

for i, j, w in edges:
    graph.add_edge(i, j, w)

mst, weight = graph.prim_mst(0)

print("\nMST边:")
for u, v, w in mst:
    print(f"  {u} ←→ {v}: {w}")

# 输出：
# ============================================================
# Prim算法测试
# ============================================================
#
# Prim算法（从顶点0开始）:
# =============================================================
# 添加边: 0 ←→ 1 (权重=2)
# 添加边: 1 ←→ 4 (权重=1)
# 添加边: 1 ←→ 2 (权重=3)
# 添加边: 0 ←→ 3 (权重=4)
# 添加边: 3 ←→ 5 (权重=7)
#
# MST总权重: 17
#
# MST边:
#   0 ←→ 1: 2
#   1 ←→ 4: 1
#   1 ←→ 2: 3
#   0 ←→ 3: 4
#   3 ←→ 5: 7