写出普利姆算法找出最小生成树的伪代码

1. 初始化一个空的最小生成树集合M，将一个任意节点加入M中。
2. 从剩余的节点中选择一个与M中节点相连的边权最小的节点v，将v加入M中。
3. 重复步骤2，直到所有节点都被加入M中。
4. 返回M。

注意：这是一个非常基础的算法，实际应用中可能需要进行优化和改进。

相关问题

普利姆算法最小生成树边的集合

### 构建最小生成树时所使用的边的集合

在构建最小生成树的过程中，普利姆算法通过逐步增加权重最低的边来扩展当前的生成树。初始状态下，任意选取一个顶点作为起始节点并将其加入到已访问节点集（白色点），其余未被选中的节点则构成待处理节点集（蓝色点）。每次迭代过程中，寻找连接这两个集合之间具有最短长度的一条或多条边（紫色边），并将对应的节点及其关联边纳入正在生长的最小生成树内。

具体实现如下：

import sys
from collections import defaultdict


def prim_algorithm(graph, start_vertex):
    mst_edges = []  # 存储最终得到的最小生成树中的所有边
    
    visited = {start_vertex}
    while len(visited) != len(graph):  
        min_edge = None
        for u in visited:    
            for v, weight in graph[u]:
                if v not in visited and (min_edge is None or weight < min_edge[2]):
                    min_edge = (u, v, weight)

        if min_edge:
            mst_edges.append(min_edge)
            visited.add(min_edge[1])
            
    return mst_edges

此代码片段展示了如何利用普利姆算法找到给定图`graph`的一个最小生成树，并返回该树内的所有边组成的列表`mst_edges`[^1]。这里假设输入是一个邻接表形式表示的无向加权图，在每一轮循环里都会挑选出一条能够使得新旧两部分相连且代价最小的新边直到遍历完所有的顶点为止[^3]。

数学建模最小生成树建模与求解，给出问题描述，求解过程，程序代码，数据列表，图形显示。

### 关于数学建模中最小生成树的相关信息

#### 问题描述
在图论中，给定一个无向带权连通图 \( G=(V,E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。每条边都有对应的权重表示连接两个节点的成本。最小生成树 (Minimum Spanning Tree, MST) 的问题是找到一棵包含所有顶点的子树，使得这棵树上的总边权之和最小。

#### 求解过程
对于求解最小生成树的问题，存在两种经典的贪心算法——克鲁斯卡尔(Kruskal)算法和普利姆(Prim)算法。这两种方法都能有效地找出加权无向图中的MST[^1]。

- **Kruskal 算法**: 将所有的边按照从小到大排序；依次选取最短的一条未被加入集合S的边(u,v)，如果这条边不会形成环，则将其添加至当前森林F中；

- **Prim 算法**: 从任意一点出发构建一颗树T，在每次迭代过程中从未访问过的相邻结点中挑选距离最近的一个作为新的起点继续扩展直到遍历整个网络。

#### MATLAB 实现代码
以下是利用MATLAB内置函数`minspantree()`来寻找最小生成树的例子：

% 创建邻接矩阵 A 表示有权重的无向图
A = [
    0     8     5     inf;
    8     0     7     9 ;
    5     7     0     6 ;
    Inf   9     6     0 ];

G = graph(A,'upper'); % 构造graph对象
plot(G);              % 绘制原始图结构

[T,pred] = minspantree(G);
figure; plot(T);      % 显示最小生成树的结果

这段脚本首先定义了一个简单的四节点完全图及其相应的邻接矩阵 `A` ，接着调用了 `minspantree()` 函数得到该图对应的最大生成树 T 及前驱数组 pred 。最后分别绘制了原图以及计算所得的最小生成树图像。

#### 数据列表
假设有一个如下表所示的城市间道路长度的数据表格用于测试上述算法:

| City | Beijing | Shanghai | Guangzhou |
|------|---------|----------|-----------|
|Beijing| 0 | 1234 km | 2000 km |
|Shanghai| 1234 km | 0 | 1500 km |
|Guangzhou| 2000 km | 1500 km | 0 |

此数据可以转换成适合输入给 Kruskal 或 Prim 算法的形式，即为一个二维数组或稀疏矩阵形式存储各城市间的直达路径成本。

#### 图形显示
通过MATLAB或其他绘图工具，可以根据实际需求调整图形样式以更好地呈现结果。例如设置不同的颜色区分不同类型的边（属于MST还是不属于）、标注具体的数值标签等特性增强可读性和美观度。