prim算法

prim算法：

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define loop(i,n) for(int i=0;i<(n);i++)
#define loop2(i,n) for(int i=1;i<=(n);i++)

const int maxn=10;
int inf=99999999;
int e[maxn][maxn];
int book[maxn],dis[maxn];

int n,m,xmin,xcount,sum;//xcount用来记录生成树中顶点的个数，sum用来存储路径之和

void test()
{   
  freopen("kruskal.in","r",stdin);  
  //freopen("kruskal.out","w",stdout); 
  int t1,t2,t3,j;

  cin>>n>>m;
  loop2(i,n)  //初始化
    loop2(j,n)
      if(i==j)e[i][j]=0;
      else e[i][j]=inf;
  loop2(i,m)  //开始读入边数据
  {
    cin>>t1>>t2>>t3;
    e[t1][t2]=t3;
    e[t2][t1]=t3;
    //cout<<t1<<" "<<t2<<":"<<t3<<endl;
  }

  loop2(i,n)  //初始化dis数组，这里是1号l顶点到各个顶点的初始距离，因为当前生成树中只有1号顶点
    dis[i]=e[1][i];
  //Prim核心部分开始，将1号顶点加入生成树
  book[1]=1; //这里用book来标记一个顶点是否已经加入生成树
  xcount++;
  while(xcount<n)
  {
    xmin=inf;
    loop2(i,n)
    {
      if(book[i]==0 && dis[i]<xmin)
      {
        xmin=dis[i];
        j=i;
      }
    }
    book[j]=1;
    xcount++;
    sum+=dis[j];
    loop2(k,n)  //扫描当前顶点j的所有边，再以j为中间点，更新生成树到每一个非树顶点的距离
      if(book[k]==0 && dis[k]>e[j][k]) 
        dis[k]=e[j][k];
  }
  cout<<sum<<endl; 
}

int main () 
{        
    test();        
    return 0;
}

test data:

6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2