建立一个带权无向图的邻接矩阵存储，再从0号顶点出发用Prim算法求该图的最小生成树，按顺序输出所得到的各条边

好的,我来为您解释如何使用邻接矩阵存储带权无向图,并使用Prim算法求最小生成树,同时按顺序输出所得到的各条边。

1. 建立邻接矩阵:
首先,我们需要建立一个二维数组来表示图的邻接矩阵。假设图有n个顶点,那么我们就创建一个n*n的矩阵。对于每一条边(u,v,w),我们将在矩阵的[u][v]和[v][u]位置填入权重w。如果两点之间没有边,则填入一个特殊值(如∞)表示无穷大。

2. Prim算法步骤:
a) 初始化:
- 创建一个大小为n的数组key,用于存储连接顶点的最小权重。
- 创建一个大小为n的数组parent,用于存储最小生成树的父节点。
- 创建一个大小为n的布尔数组inMST,用于标记顶点是否已经包含在最小生成树中。
- 将起始点(0号顶点)的key值设为0,其他顶点的key值设为∞。
- 将inMST数组的所有值设为false。

b) 主循环:
- 重复n次:
- 找到key值最小的、尚未包含在MST中的顶点u。
- 将u标记为已包含在MST中。
- 对于u的所有邻接顶点v:
- 如果v尚未包含在MST中,且边(u,v)的权重小于v的当前key值:
- 更新v的key值为边(u,v)的权重。
- 将u设为v的父节点。

3. 输出结果:
- 遍历parent数组,对于每个顶点(除了起始点),输出边(parent[i], i, key[i])。

下面是使用Python实现的代码示例:

import sys

def prim(graph):
    n = len(graph)
    key = [sys.maxsize] * n
    parent = [None] * n
    inMST = [False] * n
    key[0] = 0

    for _ in range(n):
        u = min_key(key, inMST)
        inMST[u] = True

        for v in range(n):
            if (graph[u][v] > 0 and not inMST[v] and
                    graph[u][v] < key[v]):
                key[v] = graph[u][v]
                parent[v] = u

    print_mst(parent, graph)

def min_key(key, inMST):
    min_val = sys.maxsize
    min_index = -1
    for i in range(len(key)):
        if key[i] < min_val and not inMST[i]:
            min_val = key[i]
            min_index = i
    return min_index

def print_mst(parent, graph):
    print("Edge \tWeight")
    for i in range(1, len(parent)):
        print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")

# 示例图
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(graph)

这段代码会输出最小生成树的所有边及其权重。