如何求mst中所有顶点对的最大路径边

# 定义图的邻接矩阵表示
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

# Prim算法求解最小生成树
def prim_mst(graph):
    n = len(graph)
    # 初始化最小生成树的顶点集合和边集合
    mst_set = set()
    mst_edges = []
    # 任选一个顶点作为起始点
    start = 0
    mst_set.add(start)
    while len(mst_set) < n:
        min_weight = float('inf')
        min_edge = None
        for u in mst_set:
            for v in range(n):
                if v not in mst_set and graph[u][v] > 0 and graph[u][v] < min_weight:
                    min_weight = graph[u][v]
                    min_edge = (u, v)
        mst_set.add(min_edge[1])
        mst_edges.append(min_edge)
    return mst_edges

# DFS求解最大路径边
def dfs_max_path(graph, start, end, visited, max_weight):
    visited[start] = True
    if start == end:
        return max_weight
    for i in range(len(graph)):
        if not visited[i] and graph[start][i] > 0:
            max_weight = max(max_weight, graph[start][i])
            max_weight = dfs_max_path(graph, i, end, visited, max_weight)
    return max_weight

# 求解MST中所有顶点对的最大路径边
def max_path_in_mst(graph):
    mst_edges = prim_mst(graph)
    n = len(graph)
    max_weights = [[0] * n for _ in range(n)]
    for edge in mst_edges:
        u, v = edge
        visited = [False] * n
        max_weight = dfs_max_path(graph, u, v, visited, 0)
        max_weights[u][v] = max_weight
        max_weights[v][u] = max_weight
    return max_weights

# 测试
max_weights = max_path_in_mst(graph)
for i in range(len(max_weights)):
    for j in range(len(max_weights[i])):
        print(f"顶点{i}到顶点{j}的最大路径边为：{max_weights[i][j]}")