次小生成树prim算法

次小生成树Prim算法是一种用于解决最小生成树问题的算法。它是基于Prim算法的改进版本，用于找到次小生成树。下面是一个示例代码来演示次小生成树Prim算法的实现：

import sys

def prim(graph):
    num_vertices = len(graph)
    key = [sys.maxsize] * num_vertices
    parent = [None] * num_vertices
    mst_set = [False] * num_vertices

    key[0] = 0
    parent[0] = -1

    for _ in range(num_vertices - 1):
        min_key = sys.maxsize
        min_index = -1

        for v in range(num_vertices):
            if not mst_set[v] and key[v] < min_key:
                min_key = key[v]
                min_index = v

        mst_set[min_index] = True

        for v in range(num_vertices):
            if (
                graph[min_index][v] != 0
                and not mst_set[v]
                and graph[min_index][v] < key[v]
            ):
                key[v] = graph[min_index][v]
                parent[v] = min_index

    return parent

# 示例图的邻接矩阵表示
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],
]

mst = prim(graph)
print("次小生成树的边：")
for i in range(1, len(mst)):
    print(f"{mst[i]} - {i}: {graph[i][mst[i]]}")

这段代码使用邻接矩阵表示图，并通过次小生成树Prim算法找到次小生成树的边。算法的核心思想是通过不断选择权值最小的边来构建生成树，直到生成树包含所有的顶点。次小生成树Prim算法与Prim算法的区别在于，次小生成树Prim算法在选择边的过程中会排除最小生成树的边。