approxmsttsp.cpp

自己编写的

#include <iostream>
using namespace std;
const int vexMax = 30;
typedef struct edge{
	int begin;   //  保存边的起始顶点
	int end;     //  保存边的结束顶点
	int weigh;   //  保存边的权值
}Edge;


void Prim(int g[][vexMax],Edge e[],int num,int v0)        //prim算法
{
	bool visited[vexMax];     
	memset(visited,false,sizeof(visited)); // 置初值
	int weigh[vexMax];                     // 保存权重
	int neigh[vexMax];                     // 保存邻居信息
	int i,j;
	visited[v0] = true;                // 起始顶点，这里选为顶点0
	for(i = 0; i < num; i++){
		weigh[i] = g[v0][i];
		// if(g[v0][i] == 0)  这两句可以用来处理没有边的情况
		//	weigh[i] = max;
		neigh[i] = v0;
	}
	int k = 0;           
	for(i = 1; i < num; i++){          // 循环次数，选取其余n-1个顶点
		int u = v0;
		int min = 32767;           // 边可能取到的最大权值
		for(j = 0; j < num; j++){
			if(!visited[j] && weigh[j] < min){  // 选取新加入的顶点
				min = weigh[j];
				u = j;            
			}
		}
		if(u == v0)
			return;          // 该图非连通
		visited[u] = true;             // 标记该顶点已经访问过
		e[k].begin = neigh[u];
		e[k].end = u;
		e[k].weigh = weigh[u];
		++k;
		//更新weigh的值，进入下一轮循环
		for(j = 0; j < num; j++){
			if(!visited[j] && g[u][j] < weigh[j] && g[u][j]){ // g[u][j] != 0 表示有边
				weigh[j] = g[u][j];                           // 只有有边才更新
				neigh[j] = u;
			}
		}
		
	}
	
}
int main()
{
	int Graph[vexMax][vexMax]; // 图的邻结矩阵
	int n;                     //假设图为方阵
	int i,j;
	scanf("%d",&n);            //输入顶点数
	for(i = 0; i < n; i++)      //构造图的邻接矩阵
		for(j = 0; j < n; j++)
			scanf("%d",&Graph[i][j]);
		Edge t[vexMax];
		Prim(Graph,t,n,0);
		for(i = 0; i < n-1; i++)
			printf("%d %d %d\n",t[i].begin+1,t[i].end+1,t[i].weigh);
		
		return 0;
}