生成树（Spanning Tree）是图论中的一个概念，它是一个连通无环的子图，并且包含图的所有顶点。换句话说，生成树是原图中通过一些边连接所有顶点形成的子图。

在计算图中生成树的方法中，常用的有Prim算法和Kruskal算法。

• Prim算法：从任意一个顶点开始，每次选择一条与已选顶点集合相连的边，将这条边的另一端点加入已选顶点集合。重复此过程直到所有顶点都被选入已选顶点集合中。

• Kruskal算法：按照边的权值从小到大的顺序添加边，如果添加这条边不会形成环，就将其添加到生成树中。重复此过程直到所有顶点都在生成树中。

注意，如果图有多个生成树，那么生成的生成树可能会有所不同。另外，在生成树中，可能会有一些边的权值为无穷大（即这条边不存在于生成树中）。

最小生成树是一种用于求解最小权重连通图的算法，它是一种构建最小权重连通图的算法。最小生成树的基本思想是从一个点出发，每次选择最小权重的边，直到所有的点都被连接起来，这样就可以构建出一棵最小权重的树，也就是最小生成树。

在连通网的所有生成树中，所有边的代价和最小的生成树被称为最小生成树。最小生成树可能不唯一，构成最小生成树的准则有：

1. 必须只使用该网络中的边来构造最小生成树。

2. 必须使用有且仅使用n-1条边来连接网络中的n个顶点。

3. 不能使用产生回路的边。

最小生成树的算法有很多，其中最常用的是Prim算法和Kruskal算法。Prim算法是一种贪心算法，它从一个点出发，每次选择最小权重的边，直到所有的点都被连接起来。Kruskal算法是一种分支定界算法，它从一个点出发，每次选择最小权重的边，直到所有的点都被连接起来。

最小生成树的应用非常广泛，它可以用来求解最小权重连通图的最小权重路径，也可以用来求解最小权重连通图的最短路径。此外，最小生成树还可以用来求解最小权重连通图的最小权重生成树，以及最小权重连通图的最小权重生成树的最小权重路径。总之，最小生成树是一种用于求解最小权重连通图的算法，它可以用来求解最小权重连通图的最小权重路径，也可以用来求解最小权重连通图的最短路径。它的应用非常广泛，可以用来解决许多实际问题，因此有着重要的研究价值。

Prim算法是一种求解最小生成树的贪心算法。它的基本思想是从一个顶点开始，每次选择一条连接已选顶点和未选顶点的最小权值的边，将这条边的另一端点加入已选顶点集合中，重复此过程直到所有顶点都被选入已选顶点集合中。

以下是Prim算法的步骤：

1. 初始化：选择一个起始顶点作为最小生成树的根节点，并将其加入已选顶点集合中。

2. 查找最小权值：在所有连接已选顶点和未选顶点的边中，找到权值最小的边。

3. 更新最小生成树：将这条边的另一端点加入已选顶点集合中，并更新最小生成树。

4. 重复步骤2和3，直到所有顶点都被选入已选顶点集合中。

以下是C++实现Prim算法的示例代码：

#include <iostream>  
#include <vector>  
#include <queue>  
#include <climits>  
  
using namespace std;  
  
const int MAX_N = 100; // 最大节点数  
vector<pair<int, int>> adj[MAX_N]; // 邻接表  
int dist[MAX_N]; // 存储从起点到各顶点的最小距离  
bool vis[MAX_N]; // 记录顶点是否被访问过  
  
void prim() {  
    int n, m; // n为节点数，m为边数  
    cin >> n >> m;  
    for (int i = 0; i < m; i++) {  
        int u, v, w;  
        cin >> u >> v >> w;  
        adj[u].push_back(make_pair(v, w));  
        adj[v].push_back(make_pair(u, w)); // 无向图，添加反向边  
    }  
    fill(dist, dist + n, INT_MAX); // 初始化距离数组为无穷大  
    dist[0] = 0; // 将起点到起点的距离设为0  
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 存储边的最小堆  
    pq.push(make_pair(0, 0)); // 将起点加入最小堆中  
    vis[0] = true; // 将起点标记为已访问  
    while (!pq.empty()) {  
        int u = pq.top().second; // 取出最小堆中的最小权值边起点  
        pq.pop();  
        for (int i = 0; i < adj[u].size(); i++) {  
            int v = adj[u][i].first;  
            int w = adj[u][i].second;  
            if (!vis[v] && dist[v] > w) { // 如果顶点v未被访问过，且从起点到v的距离小于当前最小距离，则更新最小距离和最小堆  
                dist[v] = w;  
                pq.push(make_pair(dist[v], v)); // 将边加入最小堆中  
                vis[v] = true; // 将顶点v标记为已访问  
            }  
        }  
    }  
    for (int i = 1; i < n; i++) { // 输出最小生成树中的边和权值  
        cout << i << " - " << dist[i] << endl;  
    }  
}

Kruskal算法是一种求解最小生成树的贪心算法。它的基本思想是从所有边中选择权值最小的边，如果这条边不会与已选边构成环，则将其加入最小生成树中，重复此过程直到所有顶点都被连接起来。

以下是Kruskal算法的步骤：

1. 将所有边按照权值从小到大排序。

2. 初始化最小生成树为空。

3. 遍历排序后的边，对于每一条边，判断是否与已选边构成环。如果不构成环，则将其加入最小生成树中。

4. 重复步骤3，直到所有顶点都被连接起来或者无法再找到满足条件的边为止。

以下是C++实现Kruskal算法的示例代码：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <queue>  
#include <climits>  
  
using namespace std;  
  
const int MAX_N = 100; // 最大节点数  
vector<pair<int, int>> adj[MAX_N]; // 邻接表  
int parent[MAX_N]; // 记录每个顶点的父节点  
int rank[MAX_N]; // 记录每个顶点的秩  
int n, m; // n为节点数，m为边数  
  
void find(int x) {  
    if (parent[x] != x) {  
        parent[x] = find(parent[x]);  
    }  
}  
  
void union_(int x, int y) {  
    int px = find(x);  
    int py = find(y);  
    if (rank[px] < rank[py]) {  
        parent[px] = py;  
    } else if (rank[px] > rank[py]) {  
        parent[py] = px;  
    } else {  
        parent[px] = py;  
        rank[py]++;  
    }  
}  
  
void kruskal() {  
    int u, v, w;  
    priority_queue<pair<int, pair<int, int>>> pq; // 存储边的最小堆，按照权值从小到大排序  
    for (int i = 0; i < m; i++) {  
        cin >> u >> v >> w;  
        adj[u].push_back(make_pair(v, w));  
        adj[v].push_back(make_pair(u, w)); // 无向图，添加反向边  
        pq.push(make_pair(w, make_pair(u, v))); // 将边加入最小堆中  
    }  
    fill(parent, parent + MAX_N, 0); // 初始化父节点数组为0，表示每个顶点都是自己的根节点  
    fill(rank, rank + MAX_N, 0); // 初始化秩数组为0，表示每个顶点的秩为0  
    while (!pq.empty()) {  
        int w = pq.top().first; // 取出最小堆中的最小权值边  
        pq.pop();  
        int u = pq.top().second.first; // 取出最小堆中的最小权值边的起点和终点  
        int v = pq.top().second.second;  
        pq.pop();  
        if (find(u) != find(v)) { // 如果起点和终点的根节点不同，则将边加入最小生成树中，并合并两个连通分量  
            union_(u, v);  
            cout << u << " - " << v << " " << w << endl; // 输出最小生成树中的边和权值  
        } else { // 如果起点和终点的根节点相同，则将这条边舍弃，因为它会与已选边构成环  
            cout << "Discard edge: " << u << " - " << v << " " << w << endl; // 输出舍弃的边和权值  
        }  
    }  
}