在数据结构中我们知道最小生成树有两种实现方法，这两种方法一定要熟练，其中prim方法开了两个辅助数组vis[]和dis[]；kruskal方法采用了并查集并可以和优先队列（也可以直接用sort排序）结合起来，下面是个人两种方法在邻接表中的实现代码：
#include<iostream> #include<vector> #include<queue> using namespace std; const int maxv=1000; const int maxe=1000; const int inf=100000000; int n,e;// 结点数，边数 struct node{ int vex,weight; }; vector<node>Adj[maxv];//定义邻接表 //prim算法部分 bool vis[maxv];//区别访问和未访问的集合 int dis[maxv];//更新各结点到集合最短距离 int prim() {//返回最小生成树之和 for(int i=0;i<n;i++){ //初始化 vis[i]=false; dis[i]=inf; } vis[0]=true; //v0点入集合 int k=0,min;//标记当前入集合结点 int sum=0;//记录最小路径和 for(int j=1;j<n;j++) { //剩余n-1个结点 min=inf; for(int i=0;i<Adj[k].size();i++){ //更新dis int v=Adj[k][i].vex; if(Adj[k][i].weight<dis[v]) dis[v]=Adj[k][i].weight; } for(int i=0;i<n;i++) { if(!vis[i]&&dis[i]<min) { k=i; min=dis[i]; } } if(min==inf)return -1;//图不连通 sum+=min; vis[k]=true; } return sum; } //kruskal算法部分 int father[maxe];//并查集 struct edge{ int x,y;//边两顶点 int weight;//边权 edge(int a,int b,int c){ x=a; y=b; weight=c; } edge(){ } }Edge[maxe]; struct cmp{ bool operator ()( int a,int b){ return Edge[a].weight>Edge[b].weight; } }; priority_queue<int,vector<int>,cmp>q;//优先队列存放最小边权下标 int kruskal() { int sum=0;//记录最小路径和 for(int i=0;i<e;i++) {father[i]=i;//并查集初始化 q.push(i) ;//优先队列存放边 } int temp=q.top();q.pop(); //先选出第一条边 sum+=Edge[temp].weight; int k=Edge[temp].x; //标记该集合 father[Edge[temp].y] =k; for(int i=2;i<n;i++) {//选剩下n-2条边 while(father[Edge[temp].x]==father[Edge[temp].y]&&!q.empty()) { temp=q.top();q.pop(); //选出非闭环的边 } if(father[Edge[temp].x]==father[Edge[temp].y])//先不出边 return -1; sum+=Edge[temp].weight; //标记该集合 father[Edge[temp].y] =father[Edge[temp].x]=k; //并入集合 ,路径压缩 } return sum; } int main(){ scanf("%d%d",&n,&e); int x,y,w; node temp; for(int i=0;i<e;i++) //初始化邻接表和边表 { scanf("%d%d%d",&x,&y,&w); temp.vex=y;temp.weight=w; Adj[x].push_back(temp); edge k(x,y,w); Edge[i]=k; } printf("%d\n",prim()) ; printf("%d\n",kruskal()) ; return 0; }
这个部分应该多刷题以熟练应用，算是一个重点。
