mst_prim.cpp

最小生成树的几种算法的实现

//poj 2560
//连通图的prim算法
#include <cstdio>

const int INF = 2147483647;
const int N = 101;
typedef double value_type ;


int n;  //the length of g graph
value_type g[N][N],d[N],q[N]; //int or double 
int cost[N];
bool visit[N]; 


void prim()
{
	int i, j, k, id = 0,state = 0;

	value_type min,railroad,road;

	for(i=0; i<n; i++) //not forget to initial the visit array 
		visit[i] = false;

	for(i=0; i<n; i++ )
		d[i] = g[0][i];    //initial the d array 
	
	visit[0] = true; //vertex 0 is visited. 
	
	for(i=1; i<n; i++) //total edge is p-1 
	{
		min = INF;  
          
		for(j=0; j<n; j++ )  // find next min
			if(visit[j]==0 && d[j]!=-1 && d[j]<min )
			{
				min = d[j];
                k = j;    
            }
		visit[k] = 1;       // visit k
		
		q[id++] = min;      // add to mst
		
		for(j=0; j<n; j++)  // refresh d[j]
			if(visit[j]==0 && g[k][j]>0 && ( d[j]==-1 || g[k][j]<d[j] ) )
				d[j] = g[k][j];
	}
	raiilroad=road=0;
} 

double x[N],y[N];

int main()
{
	int r,no;
	scanf("%d",&no);
    while(no--)
	{
		scanf("%d%d",&n,&r);
        int i,j,k;
        for(i=0; i<n; i++)
			for(j=0; j<n; j++)
				g[i][j] = -1;//i点与j点之间的距离，若-1表示没有连接，无向图
		for(i=0; i<n; i++)
			scanf("%lf%lf",&x[i],&y[i]); 
		for(i=0; i<n-1; i++)
			for(j=i+1; j<n; j++)
				g[j][i] = g[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		prim();
	}
	return 0;
}