写一个最小生成树的实验报告，写出详细步骤，并用C++写出完整代码

实验目的：
学习最小生成树的算法，了解Kruskal和Prim算法的实现过程，掌握使用C++实现最小生成树的方法。

实验原理：
最小生成树是指在一个带权连通图中，选择一些边使得这些边的权值之和最小，并且这些边构成一棵树。常用的最小生成树算法有Kruskal算法和Prim算法。

Kruskal算法：按照边权值从小到大的顺序将边加入到生成树中，若加入该边会形成环，则不加入该边，直到生成树中有n-1条边为止。Kruskal算法的时间复杂度为O(ElogE)。

Prim算法：从一个点出发，将与该点相连的边加入到一个优先队列中，每次从队列中选出权值最小的边加入到生成树中，并将新加入的点的边继续加入队列，直到生成树中有n-1条边为止。Prim算法的时间复杂度为O(ElogV)。

实验步骤：
1.读入图的邻接矩阵或邻接表
2.选择Kruskal或Prim算法实现最小生成树
3.输出最小生成树的边集合以及权值之和

C++代码实现：

Kruskal算法实现：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],w[M],idx;
int p[N];
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
struct Edge
{
    int a,b,w;
    bool operator < (const Edge &t) const
    {
        return w<t.w;
    }
}edges[M];
int kruskal()
{
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            cnt++;
            if(cnt==n-1) break;
        }
    }
    if(cnt<n-1) return -1;
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i]={a,b,c};
    }
    int t=kruskal();
    if(t==-1) puts("impossible");
    else printf("%d\n",t);
    return 0;
}

Prim算法实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
    heap.push({0,1});
    int res=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        res+=distance;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>w[i])
            {
                dist[j]=w[i];
                heap.push({dist[j],j});
            }
        }
    }
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    int t=prim();
    printf("%d\n",t);
    return 0;
}

实验结论：
本次实验通过Kruskal算法和Prim算法实现了最小生成树的生成，了解了它们的实现过程，并掌握了使用C++实现最小生成树的方法。